Дан массив целых чисел, изначально заполненный нулями. С ним необходимо производить два типа операций:
! i x - присвоить ячейке i значение x;
? l r - узнать сумму значений на отрезке [l, r].
Первая строка содержит размер массива n и количество запросов m (1 ≤ n ≤ (10^9
+ 7), 1 ≤ m ≤ 2 * 10^5
). За ним следуют m запросов по одному в строке.
В процессе работы программы необходимо поддерживать два числа P и Q. Изначально P = 91, Q = 47.
Запрос вида "! A B" обозначает, что в ячейку (A + P) mod n необходимо записать число (B + Q) mod (10^9
+ 7).
Запрос вида "? A B" обозначает, что необходимо посчитать сумму между элементами (A + P) mod n, (B + Q) mod n включительно. Пусть ответ равен Z. Тогда необходимо изменить числа P и Q следующим образом:
P = (P * 31) + Z mod (10^9
+ 7),
Q = (Q * 29) + Z mod (10^9
+ 7).
Нумерация элементов начинается с нуля.
Все входные числа не превосходят 10^9
+ 7.
Для каждого запроса на сумму нужно вывести ответ на него в отдельной строке.