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.

Write a program that simulates the device and answers Aladins questions.

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

## Comments