e-olymp
Problems

Возвращение блудного попугая

Возвращение блудного попугая

prb4498 В этой задаче Вовка захотел научить Кешу считать. Для этого он придумал такую игру: Вовка напишет последовательность чисел, а затем будет давать Кеше пары чисел l, r для каждой из которых попугай должен будет найти такую подпоследовательность, что сумма ее элементов

ai + ai+1 … +aj-1 + aj,

где i и j находятся между l и r, будет максимальной. Известно, что каждое утро Вовка может изменить (а может и оставить прежним) некоторое число в массиве, а вечером он задаст Кеше одну или несколько таких задачек.

Ваша задача помочь Кеше, а именно, написать программу, которая будет находить максимальную сумму при описанных выше условиях.

Входные данные

В первой строке находятся числа N, D (1N, D106) – длина последовательности и количество дней, в которые Вовка учил Кешу. Во второй строке N чисел – начальное состояние последовательности. Все числа по модулю не превышают 109. Далее следует M (1M105) чисел – количество дней, в которые Вовка изменял последовательность. В следующих M строках находится по три числа – d, x, y, где d – это номер дня, x – позиция изменяемого элемента, y – новое значение данного элемента. Гарантируется, что дни заданы в хронологическом порядке, а также каждое число не превышает D. В один день Вовка мог изменить несколько элементов. Далее следует число K (1K105) – количество дней, в которые Кеша хочет обратиться к Вам за помощью. Каждый запрос будет представлять собой два числа l, r – границы отрезка, на котором нужно посчитать максимальную сумму, а день, в который Кеша обращался к Вам с данным запросом, будет рассчитываться следующим образом:

d = (z+i) % D + 1,

где z – это ответ на предыдущий запрос (для первого запроса считать, что z = 0), i – номер текущего запроса. Все номера запросов и позиции в последовательности начинаются с единицы.

Выходные данные

Выведите K строк, в каждой по одному числу – ответу на запрос.

Time limit 5 seconds
Memory limit 256 MiB
Input example #1
5 5
1 -2 3 4 5
3
1 3 -3
3 1 10
4 5 1
3
1 5
2 4
1 5
Output example #1
9
4
14
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013