Sequence Operations and Combination Product Sum Query

Given a sequence of length (n) and a series of operations, your task is to perform the operations on the sequence and answer queries. The operations are as follows:

1. I a b c: Increase each element in the range ([a, b]) by (c).
2. R a b: Reverse the sign of each element in the range ([a, b]).
3. Q a b c: Query the sum of the products for every combination of (c) elements chosen from the range ([a, b]) modulo (19940417).

For a query operation, if (c) is greater than the number of elements in the range, the answer is (0). Note that the sequence is 1-indexed.

inputFormat

The first line contains two integers (n) and (m) where (n) is the length of the sequence and (m) is the number of operations. The second line contains (n) integers representing the initial sequence. Each of the next (m) lines represents an operation in one of the following formats:

I a b c
R a b
Q a b c

All indices are 1-indexed.

outputFormat

For each query operation Q, output the answer on a new line.

sample

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

95
26