### COCI 2009/2010, Contest #1

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.
• Generally, 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.

During the game Aladin wonders what is the total number of stones in some range of boxes.

### Input

The first line contains two integers N (1 ≤ N ≤ 1 000 000 000) and Q (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 ≤ 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, 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).

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

### Scoring

Test cases worth 30% of total points have N and Q ≤ 1000.

Test cases worth 70% of total points have Q ≤ 1000.

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

```0
3```

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

```3
2
1
0```

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

```16
0```

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

Point Value: 25 (partial)
Time Limit: 8.00s
Memory Limit: 64M

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3