Aralıq Cəmi Sorğusu
Verilmiş tam ədədlərdən ibarət bir massiv əvvəlcə sıfırlarla doldurulmuşdur. Bu massiv üzərində iki növ əməliyyat yerinə yetirilməlidir:
! i x - i indeksli elementə x dəyərini təyin etmək;
? l r - [l, r] aralığındakı elementlərin cəmini tapmaq.
Giriş məlumatları
Birinci sətirdə massiv ölçüsü n və sorğuların sayı m verilir (1 ≤ n ≤ (10^9 + 7), 1 ≤ m ≤ 2 * 10^5). Sonrakı m sətirdə hər biri bir sorğu olmaqla məlumatlar verilir.
Proqramın icrası zamanı P və Q adlı iki ədədin dəyərlərini saxlamaq lazımdır. Başlanğıcda P = 91, Q = 47.
"! A B" tipli sorğu, (A + P) mod n indeksli elementə (B + Q) mod (10^9 + 7) dəyərini təyin etmək deməkdir.
"? A B" tipli sorğu, (A + P) mod n və (B + Q) mod n indeksləri arasında olan elementlərin cəmini hesablamaq deməkdir. Cəmin nəticəsi Z-yə bərabər olduqda, P və Q ədədləri aşağıdakı kimi yenilənməlidir:
P = ((P * 31) + Z) mod (10^9 + **7`),
Q = ((Q * 29) + Z) mod (10^9 + **7`).
Elementlərin indekslənməsi sıfırdan başlayır.
Bütün giriş ədədləri 10^9 + 7-dən böyük deyil.
Çıxış məlumatları
Hər bir cəm sorğusunun cavabını ayrıca sətirdə çıxış edin.