Description

There is a sequence of length $n$ with three operations:

1. I a b c means adding $c$ to all elements in the interval $[a,b]$.
2. R a b means turning all elements in the interval $[a,b]$ into their opposites (negating them).
3. Q a b c means querying the value of the sum of products over all ways to choose $c$ numbers from the interval $[a,b]$, taken $\mod 19940417$.

Input Format

The first line contains two integers $n, q$, denoting the sequence length and the number of operations.

The second line contains $n$ integers, representing the sequence.

Each of the next $q$ lines contains one operation, either I a b c, R a b, or Q a b c, with meanings as described above.

Output Format

For each query, output the value of the sum of products over all ways to choose $c$ numbers from the specified interval, taken $\mod 19940417$.

5 5
1 2 3 4 5
I 2 3 1
Q 2 4 2
R 1 5
I 1 3 -1
Q 1 5 1

40
19940397

Hint

Sample explanation:

After the first operation, the sequence becomes 1 3 4 4 5.

The result of the first query is $3 \times 4 + 3 \times 4 + 4 \times 4 = 40$.

After the R operation, it becomes -1 -3 -4 -4 -5.

After the I operation, it becomes -2 -4 -5 -4 -5.

The result of the second query is $(-2)+(-4)+(-5)+(-4)+(-5)=-20$.

Constraints:

For $100\%$ of the testdata, $n \leq 50000, q \leq 50000$. The absolute value of each element in the initial sequence is $\leq 10^9$. It is guaranteed that $[a,b]$ is a valid interval. In operation I, $|c| \leq 10^9$. In operation Q, $1 \leq c \leq \min(b-a+1,20)$.

Translated by ChatGPT 5