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

The first line contains two integers ~N, Q~ ~(1 \le N \le 1\,000\,000\,000)~ ~(1 \le Q \le 50\,000)~, 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 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 \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\%~ total points have ~N~ and ~Q \le 1\,000~.

Test cases worth ~70\%~ total points have ~Q \le 1\,000~.

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 ~\{1 \bmod 2, 2 \bmod 2, 3 \bmod 2, 4 \bmod 2, 5 \bmod 2, 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