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

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

a_i + a_i+1 … +a_j-1 + a_j,

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

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

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

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

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

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

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

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