A12950 | Product Tuples

While roaming the mystic areas of Stonefalls, in order to drop legendary loot, an adventurer was given a quest as follows. He was given an array $A = {a_1,a_2,...,a_N }$ of length $N$ , and a number $K$ .

Define array $B$ as $B(q, A) = $ { $q-a_1, q-a_2, ..., q-a_N$ }. Define function $F$ as $F(B,K)$ being sum of products of all $K$ -tuples of elements in array $B$ . For example, if the array $B$ is $[2,3,4,5]$ , and with $K=3$ , sum of products of all 3-tuples is $$$$F(B, 3) = 2*3*4+2*3*5+3*4*5+2*4*5 $$ </p><p>He was then given a number Q, number of queries of two types: </p><ul> <li> Type 1: Given $q$ , $i$ , and $d$ calculate $F(B(q, A), K)$ where we make change to initial array as $A\[i\] = d$ . </li><li> Type 2: Given $q$ , $L$ , $R$ , and $d$ calculate $F(B(q, A), K)$ where we make change to initial array as $A\[i\] = A\[i\] + d$ for all $i$ in range $\[L, R\]$$$ inclusive.

All changes are temporarily made to initial array, and don't propagate to following queries. Help the adventurer calculate the answer to a quest, and finally get that loot!

In the first two lines, numbers $N$ ( $1 \leq N \leq 2*10^4$ ) and $K$ ( $1 \leq K \leq N$ ), the length of initial array $A$ , and tuple size, followed by $a_1,a_2,a_3,…,a_N$ ( $0 \leq a_i \leq 10^9$ ) , elements of array $A$ , in the next line. Then follows number $Q$ ( $Q \leq 10$ ), number of queries. In the next $Q$ lines come queries of the form:

- 1 q i d, for type 1,
- 2 q L R d, for type 2,

as explained above ( $0 \leq q, d \leq 10^9, 1 \leq i,L,R \leq N$ )

Print $Q$ lines, the answers to queries, modulo $998244353$ .