[清华集训2012]序列操作

题目背景

# 滥用评测功能将被封号

题目描述

有一个长度为$n$的序列,有三个操作: 1. `I a b c`表示将$[a,b]$这一段区间的元素集体增加$c$; 2. `R a b`表示将$[a,b]$区间内所有元素变成相反数; 3. `Q a b c`表示询问$[a,b]$这一段区间中选择$c$个数相乘的所有方案的和$\mod 19940417$的值。

输入输出格式

输入格式


第一行两个数$n, q$表示序列长度和操作个数。 第二行$n$个非负整数,表示序列。 接下来$q$行每行输入一个操作`I a b c`或者`R a b`或者`Q a b c`,意义如题目描述。

输出格式


对于每个询问,输出选出$c$个数相乘的所有方案的和$\mod 19940417$的值。

输入输出样例

输入样例 #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

输出样例 #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$。 **数据范围:** 对于100%的数据,$n \leq 50000, q \leq 50000$,初始序列的元素的绝对值$\leq 10^9$,保证$[a,b]$是一个合法区间,`I`操作中$|c| \leq 10^9$,`Q`操作中$1 \leq c \leq \min(b-a+1,20)$。