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.
The first line contains two integers $N$ and $Q$ ($1 \leq N \leq 1\, 000\, 000\, 000$) ($1 \leq Q \leq 50\, 000$), 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 1\, 000\, 000$), 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).
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.
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.
Sample Input 1 | Sample Output 1 |
---|---|
6 3 2 1 6 1 1 5 1 2 2 1 6 |
0 3 |
Sample Input 2 | Sample Output 2 |
---|---|
4 5 1 1 4 3 4 2 1 1 2 2 2 2 3 3 2 4 4 |
3 2 1 0 |
Sample Input 3 | Sample Output 3 |
---|---|
4 4 1 1 4 7 9 2 1 4 1 1 4 1 1 2 1 4 |
16 0 |
Footnotes