在石瀑布的神秘区域中漫游时,为了掉落传奇战利品,一名冒险家接到了如下任务。他得到了一个长度为 $$$N$$$ 的数组 $$$A = {a_1,a_2,...,a_N }$$$ 和一个数字 $$$K$$$。
将数组 $$$B$$$ 定义为 $$$B(q, A) = $$$ { $$$q-a_1, q-a_2, ..., q-a_N$$$ }。将函数 $$$F$$$ 定义为 $$$F(B,K)$$$ 是数组 $$$B$$$ 中所有元素 $$$K$$$ 元组的乘积之和。例如,如果数组 $$$B$$$ 为 $$$[2,3,4,5]$$$,并且 $$$K=3$$$,则所有 3 元组的乘积之和为 $$$$$$F(B, 3) = 2*3*4+2*3*5+3*4*5+2*4*5$$$$$$
然后给他一个数字 Q,即两种类型的查询数量:
- 类型 1:给定 $$$q$$$、$$$i$$$ 和 $$$d$$$ 计算 $$$F(B(q, A), K)$$$,其中我们将初始数组更改为 $$$A[i] = d$$$。
- 类型 2:给定 $$$q$$$、$$$L$$$、$$$R$$$ 和 $$$d$$$ 计算 $$$F(B(q, A), K)$$$,其中我们将初始数组更改为 $$$A[i] = A[i] + d$$$,包括 $$$[L, R]$$$ 范围内的所有 $$$i$$$。
所有更改都是临时对初始数组进行的,并且不会传播到后续查询。帮助冒险家计算任务的答案,并最终获得战利品!
输入
在前两行中,数字 $$$N$$$ ($$$1 \leq N \leq 2*10^4$$$) 和 $$$K$$$ ($$$1 \leq K \leq N$$$)、初始数组 $$$A$$$ 的长度和元组大小,后跟 $$$a_1,a_2,a_3,…,a_N$$$ ($$$0 \leq a_i \leq 10^9$$$) ,数组 $$$A$$$ 的元素,在下一行。然后是数字 $$$Q$$$ ($$$Q \leq 10$$$),即查询数。接下来的 $$$Q$$$ 行中出现以下形式的查询:
- 1 q i d,对于类型 1,
- 2 q L R d,对于类型 2,
如上所述 ($$$0 \leq q, d \leq 10^9, 1 \leq i,L,R \leq N$$$)
输出
打印 $$$Q$$$ 行,查询的答案,以 $$$998244353$$$ 为模。
示例
输入 #1
5 2 1 2 3 4 5 3 1 6 1 1 1 6 5 2 2 6 2 3 1
输出 #1
85 127 63
注意
在第一个查询数组 A = [1, 2, 3, 4, 5],B = [5, 4, 3, 2, 1] 中,2 元组的乘积之和 = 85。
在第二个查询数组中 A = [1, 2, 3, 4, 2],B = [5, 4, 3, 2, 4],2元组的乘积之和 = 127
在第三个查询数组中 A = [1, 3, 4, 4, 5],B = [5, 3, 2, 2, 1],2元组的乘积之和 = 63