Description

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

• Type 1 operation with input format 1 L R A B: for each box $X$ with $L \leq X \leq R$, set its number of stones to $(X - L + 1) \times A \bmod B$, where $X$ is the index of the box.
• Type 2 operation with input format 2 L R: query the total number of stones in boxes numbered $L$ through $R$.

Input Format

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

The next $q$ lines describe the operations.

Output Format

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

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

Hint

• For $30\%$ of the testdata, $n, q \leq 10^3$.
• For $70\%$ of the testdata, $q \leq 10^3$.
• For $100\%$ of the testdata, $1 \leq A, B \leq 10^6$.

Translated by ChatGPT 5