e-olymp
Competitions

Dynamic (implicit) Segment Tree

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 (1n ≤ (109 + 7), 1m2 * 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.

Time limit 1 seconds
Memory limit 256 MiB
Input example #1
10 8
! 1 4
! 2 5
? 3 6
! 4 1
? 5 9
! 1 4
? 5 9
? 5 9
Output example #1
52
1416
42558
103
Input example #2
15 6
! 1 1
! 5 2
? 5 14
! 8 7
? 1 4
? 4 13
Output example #2
97
0
0