Range Sum Query
Range Sum Query
Given array of integers, initially filled with zeroes. Consider two types of operations:
- ! i x - assign to cell i the value of x;
- ? l r - find the sum of numbers on segment [l, r].
Input
First line contains the size of array n and number of queries m (1 ≤ n ≤ (109
+ 7), 1 ≤ m ≤ 2 * 105
). Then m queries are given, one in a line.
During program running let's maintain two numbers P and Q. Initially P = 91, Q = 47.
The query of type "**! A B**" means that in the cell (A + P) mod n one need to pt the value of (B + Q) mod (109
+ 7).
The query of type "**? A B**" means that one need to find the sum among the elements (A + P) mod n, (B + Q) mod n inclusively. Let the answer is Z. Then we need to change the numbers P and Q in the next way:
P = (P * 31) + Z mod (109
+ 7),
Q = (Q * 29) + Z mod (109
+ 7).
The numbering of elements starts with zero.
All input numbers are not greater than 109
+ 7.
Output
For each sum query print the answer is a separate line.
10 8 ! 1 4 ! 2 5 ? 3 6 ! 4 1 ? 5 9 ! 1 4 ? 5 9 ? 5 9
52 1416 42558 103
15 6 ! 1 1 ! 5 2 ? 5 14 ! 8 7 ? 1 4 ? 4 13
97 0 0