Problem Description

You are given $n$ boxes and $q$ operations. There are two types of operations:

• The first type of operation is formatted as 1 L R A B, which means to change the number of stones in boxes numbered from $L$ to $R$ to $(X-L+1) \times A \bmod B$, where $X$ is the box number.
• The second type of operation is formatted as 2 L R, which means to query the total number of stones in boxes numbered from $L$ to $R$.

Input Format

The first line contains two numbers $n$ ($1 \leq n \leq 10^9$) and $q$ ($1 \leq q \leq 5 \times 10^4$).

The next $q$ lines represent the query operations.

Output Format

For each second type of operation, output the total number of stones.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0
3

Input Sample #2

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

Output Sample #2

3
2
1
0

Input Sample #3

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

Output Sample #3

16
0

Notes

• For $30\%$ of the data, $n, q \leq 10^3$;
• For $70\%$ of the data, $q \leq 10^3$.

见题面 Input 部分

见题面 Output 部分