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 procedes to fly to the box labeled L+1, and set the number of stones there to (2?A) mod B.
• It procedes to fly to the box labeled L+2, and set the number of stones there to (3?A) mod B.
• Generaly, it visits each box labeled between L and R, and set the number of stones there to ( (X - L + 1)?A) mod B. where X is the box label.
• After it visits the box labeled R. It settles down for further instructions.

입력

• The first line contains two integers N i Q (1 ≤ N ≤ 1 000 000 000) (1 ≤ Q ≤ 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 ≤ L ≤ R ≤ N) (1 ≤ A, B ≤ 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, than it follows the format "2 L R" (1 ≤ L ≤ R ≤ N). Meaning that Aladin wonders how many stones in total are ther stones are in boxes labeled L to R (inclusive).

출력

입출력 예

input

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

output

0
3

input

4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4

output

3
2
1
0

input

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

output

16
0

SAMPLE TESTS

출처: coci 2009/2010 contest1 6/6