Aladin was walking down the path one day when he found the strangest thing: $N$ empty boxes right next to a weird alien machine. After a bit of fumbling around he got the machine to do something. The machine now accepts 4 integers $L$, $R$, $A$ and $B$. After that hitting the big red glowing button labeled “NE DIRAJ”1 causes the machine to go crazy and follow the next routine:
- Set the number of stones in the box labeled $L$ to $A$ modulo $B$.
- It procedes to fly to the box labeled $L+1$, and set the number of stones there to $(2\cdot A) \mod B$.
- It procedes to fly to the box labeled $L+2$, and set the number of stones there to $(3\cdot A) \mod B$.
- Generaly, it visits each box labeled between $L$ and $R$, and set the number of stones there to $( (X - L + 1)\cdot A) \mod B$, where $X$ is the box label.
- After it visits the box labeled $R$. It settles down for further instructions.

During the game Aladin wonders what is the total number of stones in some range of boxes.

Write a program that simulates the device and answers Aladin’s questions.

-----Input-----
The first line contains two integers $N$ and $Q$ ($1 \leq N \leq 1000000000$) ($1 \leq Q \leq 50000$), number of boxes and number of queries.

The next $Q$ lines contain information about the simulation.

If the line starts with 1, than it follows the format “1 $L$ $R$ $A$ $B$” ($1 \leq L \leq R \leq N$) ($1 \leq A, B \leq 1000000$), meaning that Aladin keyed in numbers $L$, $R$, $A$ and $B$ in the device and allowed the device to do its job.

If the line starts with 2, then it follows the format “2 L R” ($1 \leq L \leq R \leq N$), meaning that Aladin wonders how many stones in total are ther stones are in boxes labeled $L$ to $R$ (inclusive).

-----Output-----
For each query beginning with 2 output the answer to that particular query. Queries should be processed in the order they are given in the input.First sample description

The boxes start containing $\{ 0, 0, 0, 0, 0, 0\}$, 0 stones in total. After that the device sets the stones to $\{ 1 \mod 2, 2 \mod 2, 3 \mod 2, 4 \mod 2, 5 \mod 2, 0\}$ = $\{ 1,0,1,0,1,0\}$, or 3 stones in total.

-----Examples-----
Sample Input 1:
6 3
2 1 6
1 1 5 1 2
2 1 6
Sample Output 1:
0
3

Sample Input 2:
4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4
Sample Output 2:
3
2
1
0

见题面

见题面