题目描述

生活在雾之湖的冰精琪露诺，向来以智慧而著称。作为寺子屋的老学员，琪露诺可是对数学递推式了如指掌。

有一天，慧音老师想要考一考琪露诺。于是她写出了一个长度为 $m$ 的递推公式：

$$F_t=\sum_{i=1}^m K_i\times F_{t-i} \quad (t> m)$$

其中 $m,\{K_i\}$ 都是被给定的。不过，由于这个序列 $\{F_i\}$ 的初始 $m$ 项并没有被确定，所以可能存在无穷个满足这个递推式，但是初始 $m$ 项并不一致的递推数列。慧音打算选择其中 $q$ 个 $F$ ，来考考琪露诺对数列知识的掌握。

具体而言，慧音会依次告诉琪露诺，若干个 $\{F_i\}$ 的起始 $m$ 项。显然，这样就能生成无穷序列 $\{F_i\}$ 了。尽管如此，生成这么多序列并不好玩。于是慧音又创造了一个答案序列 $\{A_i\}$ ，满足初始时 $A_i=0$ 。

每当给出一个新的 $\{F_i\}$ ，慧音都要琪露诺使 $\{A_i\}$ 的第 $a,a+1,\cdots b-1,b$ 项分别加上 $F_1,F_2,F_3,\cdots,F_{b-a+1}$ 。

当然，慧音老师不想为难琪露诺，于是对于所有数字，只要输出其对 $p$ 取模的值即可。其中 $p$ 是一个被给定的常数。

---

形式化地讲述题面：给定 $n,q,m,p,\{K_1,K_2,\cdots ,K_m\}$ 。有 $q$ 次操作，每次给定一组 $a,b,\{G_1,G_2\cdots G_m\}$ ，求出无穷序列 $\{F_i\}$ ：

$$F_t=\begin{cases} G_t & t\le m \cr \sum_{i=1}^m K_iF_{t-i} & t>m \end{cases}$$

然后令 $\forall i\in [a,b] ,A_i\gets A_i+F_{i-a+1}$ 。最后分别输出 $\{A_i\}$ 的前 $n$ 项对 $p$ 取模后的结果。

输入格式

• 第一行有四个正整数 $n,q,m,p$ ，含义如题面所示。

• 第二行有 $m$ 个整数 $\{K_1,K_2,\cdots ,K_m\}$ ，表示递推式中的系数。

• 接下来 $q$ 行，每行 $2+m$ 个整数 $a,b,\{G_1,G_2,\cdots G_m\}$ ，描述一次操作。

输出格式

• 共一行， $n$ 个整数，输出 $A_i \bmod p$ 的值。

5 3 2 114514
1 1
1 3 1 1
2 5 1 1
1 5 2 0

3 2 5 4 7

20 5 4 1919810
2 5 4 3
1 20 1 1 1 1
5 12 7 6 1 2
2 18 9 0 0 1
9 11 5 4 4 1
10 14 1 0 0 0

1 10 1 1 22 75 221 850 3176 11706 43324 160379 586060 249707 351705 931555 619201 372869 1800119 1750063

提示

样例解释

对于样例 $1$ ：

• 初始时， $\{A_i\}=\{0,0,0,0,0\}$ 。

• 第一步生成了一个 $\{F_i\}=\{1,1,2,3,5\}$ ，加至 $A_1,A_2,A_3$ ，此时 $\{A_i\}=\{1,1,2,0,0\}$ 。

• 第二步生成了一个 $\{F_i\}=\{1,1,2,3,5\}$ ，加至 $A_2,A_3,\cdots ,A_5$ ，此时 $\{A_i\}=\{1,2,3,2,3\}$ 。

• 第三步生成了一个 $\{F_i\}=\{2,0,2,2,4\}$ ，加至 $A_1,A_2,\cdots ,A_5$ ，此时 $\{A_i\}=\{3,2,5,4,7\}$ 。

对于样例 $2$ ，我们既没有一个绝妙的解释，又没有足够大的空间，于是我们写不下了。

数据范围及约定

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{n} & \bm{m} & \bm{q}& \textbf{分值}\cr\hline 1 & n\le 10^4 & m\le 10 & q\le 10^3 & 10 \cr\hline 2 & n\le 10^5 & m=1 & q\le 10^5 & 20\cr\hline 3 & n\le 10^5 & m=2 & q\le 10^5 & 20\cr\hline 4 & \text{无特殊限制} & \text{无特殊限制} & \text{无特殊限制}& 50 \cr\hline \end{array}$$

• 对于 $100\%$ 的数据，满足 $ 1 \leq n\le 1\times 10^6;1\le q \leq 1.2 \times 10^5;1 \leq m \leq 15;1 \leq K_i,G_i,p \leq 10^8;1\le a\le b\le n$ 。