eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 5 seconds
Memory limit 256 MiB

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

a_i + a_i_{+1} … +a_j_{-1} + a_j,

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

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

Input data

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

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

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

Output data

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

Examples

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