问题陈述
给你一个长度序列 N, A=(A_1,A_2,\ldots,A_N),另一个长度 K, P=(P_1,P_2,\ldots,P_K).
我们现在执行以下操作 Q 对序列的操作 A.
- 的
树的 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-th 操作,考虑无限序列 B=(B_1,B_2,\ldots) 由以下线性递推关系确定,并添加 B_i to A_{l_q+i-1} 对于每个 i=1,2,\ldots,r_q-l_q+1.
- B_j=b_{q,j}\ (1\leq j \leq K)
- B_j=P_1B_{j-1}+P_2B_{j-2}+\ldots +P_KB_{j-K}\ (j > K)
求模值 998244353,每个元素 A 完成所有操作后。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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}
输出
打印取模值 998244353,元素 A 完成所有操作后。
示例输入 1
5 2 3 0 0 0 0 0 2 1 1 4 3 1 3 5 4 1 2 2 5 9
示例输出 1
3 6 9 12 6
最初, 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 is (3,6,9,12,6).
示例输入 2
1 3 1 5 1 0 1 1 1 3 1 4
示例输出 2
8
示例输入 3
10 3 5 306334866 801978559 895954374 576826717 755317213 872021310 894146017 171871727 347837426 489203653 259995927 523608184 755770553 4 7 822177140 73169010 811074390 7 8 739309938 819084714 711663615 1 9 105947194 88003242 226522376 6 8 544083472 975159386 830222368 1 9 478160947 233931690 460328037
示例输出 3
890443007 125669138 584560434 427420890 15883850 302004751 273022029 711724605 576696309 489203653