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" 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 proceeds to fly to the box labeled $L+1$, and set the number of stones there to $(2\cdot A)modB$.
• It proceeds to fly to the box labeled $L+2$, and set the number of stones there to $(3\cdot A)modB$.
• Generally, it visits each box labeled between $L$ and $R$, and set the number of stones there to $((X-L+1)\cdot A)modB$, 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 Specification

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

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

If the line starts with $1$, then it follows the format 1 L R A B $(1\le L\le R\le N)$ $(1\le A,B\le 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\le L\le R\le N)$. Meaning that Aladin wonders how many stones in total are in boxes labeled $L$ to $R$ (inclusive).

Output Specification

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.

Scoring

Test cases worth $30\mathrm{\%}$ total points have $N$ and $Q\le 1000$.

Test cases worth $70\mathrm{\%}$ total points have $Q\le 1000$.

Sample Input 1

6 3
2 1 6
1 1 5 1 2
2 1 6

Sample Output 1

0
3

Explanation for Sample Output 1

The boxes start containing $\{0,0,0,0,0,0\}$, $0$ stones in total.

After that the device sets the stones to $\{1mod2,2mod2,3mod2,4mod2,5mod2,0\}=\{1,0,1,0,1,0\}$, or $3$ stones in total.

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

Sample Input 3

4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4

Sample Output 3

16
0