Description

Given an array $a_1, a_2, \dots, a_N$ of length $N$. Let $s_1, s_2, \dots, s_q$ be all non-empty subsequences of this array, where $q = 2^n - 1$.

About lexicographical order: if the first position where two arrays $A$ and $B$ differ is $i$, and $A_i < B_i$; or $A$ is a strict prefix of $B$ (i.e., they cannot be equal), then $A$ is lexicographically smaller than $B$.

We define the hash value of an array consisting of $v_1, v_2, \dots, v_p$ as:

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

where $B, M$ are given integers.

For a given integer $K$, find the values of $h(s_1), h(s_2), \dots, h(s_K)$.

Input Format

The first line contains four integers $N, K, B, M$.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$.

Output Format

Output a total of $K$ lines. The $i$-th line should be the value of $h(s_i)$.

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

Hint

Sample Explanation

Sample $1$

$s_1 = [1], s_2 = [1, 2], s_3 = [2]$.

$h(s_1) = 1 \bmod 5 = 1, h(s_2) =(1 + 2) \bmod 5 = 3, h(s_3) = 2 \bmod 5 = 2$.

Sample $2$

$s_1 = [1], s_2 = [1], s_3 = [1, 1], s_4 = [1, 3]$.

$h(s1) = 1 \bmod 3 = 1, h(s_2) = 1 \bmod 3 = 1, h(s_3) = (1 \times 2 + 1) \bmod 3 = 0, h(s_4) = (1 \times 2 + 3) \bmod 3 = 2$.

Constraints

For $60\%$ of the testdata, $1 \le a_i \le 30$.
For $100\%$ of the testdata, $1 \le N, K, a_i \le 10^5$, $1 \le B, M \le 10^6$, and $K \le 2^N - 1$.

Notes

Translated from COCI2015-2016 CONTEST #5 T6 PODNIZOVI。

Translated by ChatGPT 5