Aladin

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 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).

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.

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

  1. “DO NOT TOUCH”