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