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