# Problem E

Podnizovi

You are given an array of integers of length $N$. Let $s_1, s_2, \ldots , s_ q$ be the lexicographically sorted array of all its non-empty subsequences. A subsequence of the array is an array obtained by removing zero or more elements from the initial array. Notice that some subsequences can be equal and that it holds $q = 2^ N - 1$.

An array $A$ is lexicographically smaller than array $B$ if $A_ i < B_ i$ where $i$ is the first position at which the arrays differ, or if $A$ is a strict prefix of array $B$.

Let us define the hash of an array that consists of values $v_1, v_2, \ldots , v_ p$ as:

\[ h(s) = (v_1 \cdot B^{p-1} + v_2 \cdot B^{p-2} + \ldots + v_{p-1} \cdot B + v_ p ) \bmod M \]where $B$, $M$ are given integers.

Calculate $h(s_1) h(s_2), \ldots , h(s_ K)$ for a given $K$.

## Input

The first line contains integers $N$, $K$, $B$, $M$ ($1 \leq N \leq 100\, 000$, $1 \leq K \leq 100\, 000$, $1 \leq B, M \leq 1\, 000\, 000$). The second line contains integers $a_1, a_2, a_3, \ldots , a_ N$ ($1 \leq a_ i \leq 100\, 000$). In all test cases, it will hold $K \leq 2^ N - 1$.

## Output

Output $K$ lines, the $j$-th line containing $h(s_ j)$.

Sample Input 1 | Sample Output 1 |
---|---|

2 3 1 5 1 2 |
1 3 2 |

Sample Input 2 | Sample Output 2 |
---|---|

3 4 2 3 1 3 1 |
1 1 0 2 |

Sample Input 3 | Sample Output 3 |
---|---|

5 6 23 1000 1 2 4 2 3 |
1 25 25 577 274 578 |