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:

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)$.

2 3 1 5
1 2

1
3
2

3 4 2 3
1 3 1

1
1
0
2

5 6 23 1000
1 2 4 2 3

1
25
25
577
274
578