Subsequence Hashes

You are given an array of $N$ integers. Sort every non-empty subsequence of that array lexicographically and call the result $s_1, s_2, \dots, s_q$. A subsequence is an array obtained by deleting zero or more elements from the original array. Several subsequences can be equal to one another, and $q = 2^N - 1$.

Array $A$ is lexicographically smaller than array $B$ if $A_i < B_i$ at the first position $i$ where the two arrays differ, or if $A$ is a strict prefix of $B$.

The hash of an array with values $v_1, v_2, \dots, v_p$ is defined as

$h(s) = (v_1 B^{p-1} + v_2 B^{p-2} + \dots + v_{p-1} B + v_p) \bmod M$

where $B$ and $M$ are given integers. For a given $K$, compute $h(s_1), h(s_2), \dots, h(s_K)$.

The first line contains the integers $N$, $K$, $B$, $M$ ($1 \le N \le 100\,000$, $1 \le K \le 100\,000$, $1 \le B, M \le 1\,000\,000$).

The second line contains the integers $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 100\,000$).

Every input satisfies $K \le 2^N - 1$.

Print $K$ lines. Line $j$ contains $h(s_j)$.

In the first example the sorted subsequences are $s_1 = [1]$, $s_2 = [1, 2]$, $s_3 = [2]$, so $h(s_1) = 1 \bmod 5 = 1$, $h(s_2) = (1 + 2) \bmod 5 = 3$ and $h(s_3) = 2 \bmod 5 = 2$.

In the second example they are $s_1 = [1]$, $s_2 = [1]$, $s_3 = [1, 1]$, $s_4 = [1, 3]$. Two elements have the value 1, so $[1]$ appears twice. The hashes are $h(s_1) = 1 \bmod 3 = 1$, $h(s_2) = 1 \bmod 3 = 1$, $h(s_3) = (1 \times 2 + 1) \bmod 3 = 0$ and $h(s_4) = (1 \times 2 + 3) \bmod 3 = 2$.