AT_past202309_o 数列の足し算

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.

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} $

Print the values, modulo $ 998244353 $ , of the elements of $ A $ after all the operations.

### Sample Explanation 1 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) $ . ### 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.