Возвращение блудного попугая
В этой задаче Вовка захотел научить Кешу считать. Для этого он придумал такую игру: Вовка напишет последовательность чисел, а затем будет давать Кеше пары чисел l, r для каждой из которых попугай должен будет найти такую подпоследовательность, что сумма ее элементов
a_i + a_i_{+1} … +a_j_{-1} + a_j,
где i и j находятся между l и r, будет максимальной. Известно, что каждое утро Вовка может изменить (а может и оставить прежним) некоторое число в массиве, а вечером он задаст Кеше одну или несколько таких задачек.
Ваша задача помочь Кеше, а именно, написать программу, которая будет находить максимальную сумму при описанных выше условиях.
Входные данные
В первой строке находятся числа N, D (1 ≤ N, D ≤ 10^6) – длина последовательности и количество дней, в которые Вовка учил Кешу. Во второй строке N чисел – начальное состояние последовательности. Все числа по модулю не превышают 10^9. Далее следует M (1 ≤ M ≤ 10^5) чисел – количество дней, в которые Вовка изменял последовательность. В следующих M строках находится по три числа – d, x, y, где d – это номер дня, x – позиция изменяемого элемента, y – новое значение данного элемента. Гарантируется, что дни заданы в хронологическом порядке, а также каждое число не превышает D. В один день Вовка мог изменить несколько элементов. Далее следует число K (1 ≤ K ≤ 10^5) – количество дней, в которые Кеша хочет обратиться к Вам за помощью. Каждый запрос будет представлять собой два числа l, r – границы отрезка, на котором нужно посчитать максимальную сумму, а день, в который Кеша обращался к Вам с данным запросом, будет рассчитываться следующим образом:
d = (z+i) % D + 1,
где z – это ответ на предыдущий запрос (для первого запроса считать, что z = 0), i – номер текущего запроса. Все номера запросов и позиции в последовательности начинаются с единицы.
Выходные данные
Выведите K строк, в каждой по одному числу – ответу на запрос.