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

1. I a b c: Add $c$ to all elements in the range $[a, b]$.
2. R a b: Replace all elements in the range $[a, b]$ with their opposites (negate them).
3. Q a b c: Query the sum of the products of all possible ways to choose $c$ elements from the range $[a, b]$, modulo $19\,940\,417$.

Input

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

The second line contains $n$ non-negative integers representing the sequence.

The next $q$ lines each contain an operation I a b c, R a b, or Q a b c, as described above.

Output

For each query, output the sum of the products of all possible ways to choose $c$ elements from the range, modulo $19\,940\,417$.

Examples

Input 1

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

Output 1

40
19940397

Note 1

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, the sequence becomes -1 -3 -4 -4 -5.

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

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

Constraints

• $10\%$ of the data: $n \leq 10$, $q \leq 10$.
• Another $30\%$ of the data: No I or R operations.
• Another $30\%$ of the data: No I operations.
• $100\%$ of the data:
  • $1 \leq n \leq 50\,000$
  • $1 \leq q \leq 50\,000$
  • The absolute value of the initial sequence elements $\leq 10^9$.
  • In I a b c, $[a, b]$ is a valid range and $|c| \leq 10^9$.
  • In R a b, $[a, b]$ is a valid range.
  • In Q a b c, $[a, b]$ is a valid range and $1 \leq c \leq \min(b-a+1, 20)$.