Azmış tutuquşunun qayıdışı
Bu məsələdə Vovka, Keşanı saymağı öyrətmək üçün bir oyun icad etdi. Oyun belədir: Vovka bir sıra ədədlər yazır və sonra Keşaya l, r cütlərini verir. Keşa, hər cüt üçün elə bir alt sıra tapmalıdır ki, onun elementlərinin cəmi
a_i + a_i+1 + … + a_j-1 + a_j,
burada i və j l və r arasında yerləşir, maksimum olsun. Məlumdur ki, hər səhər Vovka massivin bəzi ədədlərini dəyişə bilər (və ya dəyişməz buraxa bilər), axşam isə Keşaya bir və ya bir neçə belə tapşırıq verəcək.
Sizin vəzifəniz Keşaya kömək etməkdir, yəni yuxarıda təsvir olunan şərtlər altında maksimum cəmi tapacaq proqram yazmaqdır.
Giriş verilənləri
Birinci sətirdə N, D (1 ≤ N, D ≤ 10^6) ədədləri - ardıcıllığın uzunluğu və Vovkanın Keşanı öyrətdiyi günlərin sayı verilir. İkinci sətirdə N ədəd - ardıcıllığın başlanğıc vəziyyəti. Bütün ədədlər modul üzrə 10^9-dan çox deyil. Sonra M (1 ≤ M ≤ 10^5) ədədi - Vovkanın ardıcıllığı dəyişdiyi günlərin sayı verilir. Növbəti M sətirdə üç ədəd - d, x, y verilir, burada d - günün nömrəsi, x - dəyişdirilən elementin mövqeyi, y - həmin elementin yeni dəyəri. Günlərin xronoloji ardıcıllıqla verildiyi və hər bir ədədin D-dən çox olmadığı təmin edilir. Bir gün Vovka bir neçə elementi dəyişə bilərdi. Sonra K (1 ≤ K ≤ 10^5) ədədi - Keşanın sizə müraciət etmək istədiyi günlərin sayı verilir. Hər sorğu iki ədəddən ibarət olacaq - l, r - maksimum cəmi hesablamaq lazım olan seqmentin sərhədləri və Keşanın sizə bu sorğu ilə müraciət etdiyi gün aşağıdakı kimi hesablanacaq:
d = (z+i) % D + 1,
burada z - əvvəlki sorğunun cavabıdır (birinci sorğu üçün z = 0 hesab edin), i - cari sorğunun nömrəsidir. Bütün sorğu nömrələri və ardıcıllıq mövqeləri birdən başlayır.
Çıxış verilənləri
K sətir çıxarın, hər birində bir ədəd - sorğunun cavabı.