问题描述

有一个长度为 $n$ 的序列，有三个操作

1. I a b c 表示将 $[a,b]$ 这一段区间的元素集体增加 $c$，
2. R a b 表示将 $[a,b]$ 区间内所有元素变成相反数，
3. Q a b c 表示询问 $[a,b]$ 这一段区间中选择 $c$ 个数相乘的所有方案的和 $\bmod 19\,940\,417$ 的值。

输入格式

第一行两个数 $n$，$q$ 表示序列长度和操作个数。

第二行 $n$ 个非负整数，表示序列。

接下来 $q$ 行每行输入一个操作 I a b c 或者 R a b 或者 Q a b c 意义如题目描述。

输出格式

对于每个询问，输出选出 $c$ 个数相乘的所有方案的和 $\bmod 19\,940\,417$ 的值。

样例输入

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

样例解释

做完第一个操作序列变为 1 3 4 4 5。

第一次询问结果为 $3 \times 4+3 \times 4+4 \times 4=40$。

做完 R 操作变成 -1 -3 -4 -4 -5。

做完 I 操作变为 -2 -4 -5 -4 -5。

第二次询问结果为 $-2-4-5-4-5=-20$。

数据规模和约定

$10\%$ 的数据 $n\leq 10$，$q \leq 10$。

另 $30\%$ 的数据没有 I 和 R 操作。

另 $30\%$ 的数据没有 I 操作。

$100\%$ 的数据：

• $1 \leq n \leq 50\,000$
• $1 \leq q \leq 50\,000$
• 初始序列的元素的绝对值 $\leq 10^9$。
• I a b c 中保证 $[a,b]$ 是一个合法区间，$|c| \leq 10^9$。
• R a b 保证 $[a,b]$ 是个合法的区间。
• Q a b c 中保证 $[a,b]$ 是个合法的区间 $1 \leq c \leq \min(b-a+1,20)$。