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) $ を考え、 $ 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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ で割った余りを空白区切りで出力せよ。

### Sample Explanation 1 最初、 $ 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) $ です。 ### 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 $ - 入力は全て整数