O - Add Sequences Editorial /

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