\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} рядків, у кожному по одному числу -- відповіді на запит.