COCI '09 Contest 1 #6 Aladin

View as PDF

Points: 25 (partial)
Time limit: 8.0s
Memory limit: 64M

Problem types

Aladin was walking down the path one day when he found the strangest thing. 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 and . 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 to modulo .
• It procedes to fly to the box labeled , and set the number of stones there to mod .
• It procedes to fly to the box labeled , and set the number of stones there to mod .
• Generally, it visits each box labeled between and , and set the number of stones there to . where is the box label.
• After it visits the box labeled . 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 , number of boxes and number of queries.

The next lines contain information about the simulation.

If the line starts with , than it follows the format 1 L R A B , meaning that Aladin keyed in numbers and in the device and allowed the device to do its job.

If the line starts with , than it follows the format 2 L R . Meaning that Aladin wonders how many stones in total are in boxes labeled to (inclusive).

Output

For each query beginning with output the answer to that particular query.

Queries should be processed in the order they are given in the input.

Scoring

Test cases worth total points have and .

Test cases worth total points have .

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 , stones in total. After that the device sets the stones to = , or 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