# 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** (**1** ≤ **n** ≤ (`10`

+ ^{9}**7**), **1** ≤ **m** ≤ **2** * `10`

). Then ^{5}**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 (`10`

+ ^{9}**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 (`10`

+ ^{9}**7**),

**Q** = (**Q** * **29**) + **Z** mod (`10`

+ ^{9}**7**).

The numbering of elements starts with zero.

All input numbers are not greater than `10`

+ ^{9}**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