Повернення блудливого папуги
У цій задачі Вовка захотів навчити Кешу рахувати. Для цього він придумав таку гру: Вовка напише послідовність чисел, а потім буде давати Кеші пари чисел 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 рядків, у кожному по одному числу – відповіді на запит.