Description

Cirno, the ice fairy who lives at Misty Lake, has always been known for her "wisdom". As a senior student at the temple school, Cirno is very familiar with mathematical recurrences.

One day, Teacher Keine wanted to test Cirno. So she wrote down a recurrence of length $m$:

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

Here, $m$ and $\{K_i\}$ are given. However, since the first $m$ terms of the sequence $\{F_i\}$ are not fixed, there may be infinitely many recurrence sequences that satisfy this formula but have different initial $m$ terms. Keine plans to choose $q$ such sequences $F$ to test Cirno's understanding of sequences.

More specifically, Keine will tell Cirno the first $m$ terms of some $\{F_i\}$ one by one. Obviously, this determines an infinite sequence $\{F_i\}$. Still, generating so many sequences is not very fun. So Keine creates an answer sequence $\{A_i\}$, with $A_i=0$ initially.

Each time a new $\{F_i\}$ is given, Keine asks Cirno to add $F_1,F_2,F_3,\cdots,F_{b-a+1}$ to the terms $A_a,A_{a+1},\cdots,A_{b-1},A_b$ respectively.

Of course, Teacher Keine does not want to make things too hard. So for all numbers, you only need to output their values modulo $p$, where $p$ is a given constant.

---

Formally, given $n,q,m,p,\{K_1,K_2,\cdots ,K_m\}$. There are $q$ operations. In each operation, a set of $a,b,\{G_1,G_2\cdots G_m\}$ is given. Define the infinite sequence $\{F_i\}$ by:

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

Then for all $i\in [a,b]$, set $A_i\gets A_i+F_{i-a+1}$. Finally, output the first $n$ terms of $\{A_i\}$ modulo $p$.

Input Format

• The first line contains four positive integers $n,q,m,p$, with the meanings as described above.

• The second line contains $m$ integers $\{K_1,K_2,\cdots ,K_m\}$, representing the coefficients in the recurrence.

• The next $q$ lines each contain $2+m$ integers $a,b,\{G_1,G_2,\cdots G_m\}$, describing one operation.

Output Format

• Output a single line with $n$ integers, the values of $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

Hint

Sample Explanation

For sample $1$:

• Initially, $\{A_i\}=\{0,0,0,0,0\}$.

• The first step generates $\{F_i\}=\{1,1,2,3,5\}$, and adds it to $A_1,A_2,A_3$. Now $\{A_i\}=\{1,1,2,0,0\}$.

• The second step generates $\{F_i\}=\{1,1,2,3,5\}$, and adds it to $A_2,A_3,\cdots ,A_5$. Now $\{A_i\}=\{1,2,3,2,3\}$.

• The third step generates $\{F_i\}=\{2,0,2,2,4\}$, and adds it to $A_1,A_2,\cdots ,A_5$. Now $\{A_i\}=\{3,2,5,4,7\}$.

For sample $2$, we have neither a great explanation nor enough space, so we cannot write it here.

Constraints and Notes

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

• For $100\%$ of the testdata: $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$。

Translated by ChatGPT 5