AT_past202309_o 数列の足し算

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$，以及一个长度为 $K$ 的序列 $P = (P_1, P_2, \ldots, P_K)$。 现需要对序列 $A$ 执行 $Q$ 次操作。 - 第 $q$ 次操作 $(1 \leq q \leq Q)$ 给出整数 $l_q, r_q\ (1 \leq l_q \leq r_q \leq N)$，以及一个长度为 $K$ 的序列 $b_q = (b_{q,1}, b_{q,2}, \ldots, b_{q,K})$。对于第 $q$ 次操作，构造一个无限长的序列 $B = (B_1, B_2, \ldots)$，满足如下线性递推关系： - $B_j = b_{q,j}\ (1 \leq j \leq K)$ - $B_j = P_1 B_{j-1} + P_2 B_{j-2} + \ldots + P_K B_{j-K}\ (j > K)$ 然后对于每个 $i=1,2,\ldots,r_q-l_q+1$，令 $A_{l_q+i-1} \gets A_{l_q+i-1} + B_i$。 请你输出所有操作结束后，$A$ 序列中的每一个元素对 $998244353$ 取模后的值。

输入由标准输入给出，格式如下： > $N\ K\ Q\ A_1\ A_2\ \ldots\ A_N\ P_1\ P_2\ \ldots\ P_K\ l_1\ r_1\ B_{1,1}\ B_{1,2}\ \ldots\ B_{1,K}$ > $\vdots$ > $l_Q\ r_Q\ b_{Q,1}\ b_{Q,2}\ \ldots\ b_{Q,K}$

输出所有操作执行完后 $A$ 的每个元素对 $998244353$ 取模后的值。

### 样例解释 1 初始时，$A = (0, 0, 0, 0, 0, 0)$。 - 第一次操作，$B = (3, 1, 5, 11, 27, \ldots)$。操作后，$A = (3, 1, 5, 11, 0, 0)$。 - 第二次操作，$B = (4, 1, 6, 13, 32, \ldots)$。操作后，$A = (3, 1, 9, 12, 6)$。 - 第三次操作，$B = (5, 9, 23, 55, 133, \ldots)$。操作后，$A = (3, 6, 9, 12, 6)$。 最终 $A = (3, 6, 9, 12, 6)$。 ### 数据范围 - $1 \leq N, Q \leq 2 \times 10^5$ - $1 \leq K \leq 10$ - $1 \leq l_q \leq r_q \leq N$ - $0 \leq A_i, P_i, b_{q,i} < 998244353$ - 所有输入值均为整数。 由 ChatGPT 5 翻译