Time Limit: 3 sec / Memory Limit: 1024 MB
問題文
長さ 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) を考え、
i=1,2,\ldots,r_q-l_q+1 それぞれに対して、A_{l_q+i-1} に B_i を加算する。
- 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)
全ての操作を行った後の A の各要素の値を 998244353 で割った余りを求めてください。
制約
- 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}
出力
全ての操作を行った後の A の各要素の値を 998244353 で割った余りを空白区切りで出力せよ。
入力例 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) です。
- 1 回目の操作では B=(3,1,5,11,27,\ldots) です。操作後、A=(3,1,5,11,0) になります。
- 2 回目の操作では B=(4,1,6,13,32,\ldots) です。操作後、A=(3,1,9,12,6) になります。
- 3 回目の操作では B=(5,9,23,55,133,\ldots) です。操作後、A=(3,6,9,12,6) になります。
よって、全ての操作を行った後の A は (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
Problem Statement
You are given a sequence of length N, A=(A_1,A_2,\ldots,A_N), and another of length K, P=(P_1,P_2,\ldots,P_K).
We now perform the following Q operations on the sequence A.
- The q-th operation (1\leq q \leq Q) is represented by integers l_q,r_q\ (1\leq l_q \leq r_q\leq N)
and a sequence of length K, b_q = (b_{q,1},b_{q,2},\ldots,b_{q,K}).
For the q-th operation, consider the infinite sequence B=(B_1,B_2,\ldots) determined by the following linear recurrence relation, and add B_i to A_{l_q+i-1} for each 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)
Find the value, modulo 998244353, of each element of A after all the operations.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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}
Output
Print the values, modulo 998244353, of the elements of A after all the operations.
Sample Input 1
5 2 3 0 0 0 0 0 2 1 1 4 3 1 3 5 4 1 2 2 5 9
Sample Output 1
3 6 9 12 6
Initially, A=(0,0,0,0,0,0).
- In the first operation, B=(3,1,5,11,27,\ldots). After this operation, A=(3,1,5,11,0,0).
- In the second operation, B=(4,1,6,13,32,\ldots). After this operation, A=(3,1,9,12,6).
- In the third operation, B=(5,9,23,55,133,\ldots). After this operation, A=(3,6,9,12,6).
Thus, after all the operations, A is (3,6,9,12,6).
Sample Input 2
1 3 1 5 1 0 1 1 1 3 1 4
Sample Output 2
8
Sample Input 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
Sample Output 3
890443007 125669138 584560434 427420890 15883850 302004751 273022029 711724605 576696309 489203653