Recurrence Sum Update

In this problem, you are given a fixed linear recurrence relation and several update operations. The recurrence is defined as follows. For a fixed integer m and coefficients \(K_1, K_2, \dots, K_m\), an infinite sequence \(\{F_i\}\) is defined by:

$$F_t = \begin{cases} G_t, & t \le m, \\ \sum_{i=1}^m K_i \times F_{t-i}, & t > m, \end{cases} $$

For each query, you are provided with a starting segment \(\{G_1, G_2, \dots, G_m\}\) which uniquely determines the sequence \(\{F_i\}\). Then, given two indices \(a\) and \(b\) (with 1-based indexing), you update an initially zero sequence \(\{A_i\}\) by adding the first \(b-a+1\) terms of \(\{F_i\}\) to positions \(A_a, A_{a+1}, \dots, A_b\) respectively, that is:

$$A_{a+j-1} \gets A_{a+j-1} + F_j \quad \text{for } j = 1, 2, \dots, b-a+1. $$

After all queries, output the first n terms of sequence \(\{A_i\}\) modulo a given integer p.

Input Format: The input begins with four integers \(n,\ q,\ m,\ p\). The next line contains \(m\) integers representing \(K_1, K_2, \dots, K_m\). Then follow \(q\) queries. Each query consists of a line containing two integers \(a\) and \(b\) and then a line with \(m\) integers \(G_1, G_2, \dots, G_m\). It is guaranteed that the update interval length \(b-a+1\) does not exceed \(n\).

Output Format: Output the first \(n\) elements of \(\{A_i\}\) modulo \(p\) as a sequence of integers separated by spaces.

inputFormat

The first line contains four integers n, q, m, and p — the length of the output sequence, the number of queries, the order of the recurrence, and the modulo value.

The second line contains m integers: \(K_1, K_2, \dots, K_m\).

Then, there are q queries. Each query consists of two lines: the first line contains two integers a and b (denoting the starting and ending indices of the update) and the second line contains m integers: \(G_1, G_2, \dots, G_m\), which form the initial segment for the recurrence in that query.

outputFormat

Output a single line containing n space-separated integers — the first n elements of the sequence \(\{A_i\}\) after all queries, each taken modulo p.

sample

5 1 2 1000
1 1
1 5
1 1

1 1 2 3 5