eolymp
bolt
Try our new interface for solving problems
Məsələlər

Range Sum Query

Range Sum Query

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Дан массив целых чисел, изначально заполненный нулями. С ним необходимо производить два типа операций:

  • ! i x - присвоить ячейке i значение x;

  • ? l r - узнать сумму значений на отрезке [l, r].

Giriş verilənləri

Первая строка содержит размер массива n и количество запросов m (1n ≤ (10^9 + 7), 1m2 * 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.

Çıxış verilənləri

Для каждого запроса на сумму нужно вывести ответ на него в отдельной строке.

Nümunə

Giriş verilənləri #1
10 8
! 1 4
! 2 5
? 3 6
! 4 1
? 5 9
! 1 4
? 5 9
? 5 9
Çıxış verilənləri #1
52
1416
42558
103
Giriş verilənləri #2
15 6
! 1 1
! 5 2
? 5 14
! 8 7
? 1 4
? 4 13
Çıxış verilənləri #2
97
0
0