Problem Description

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

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

The hash value of an array composed of $v_1, v_2, \dots, v_p$ is defined 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$ and $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 consists of $K$ lines, where the $i$-th line is the value of $h(s_i)$.

Sample Input and Output

Sample Input #1

2 3 1 5
1 2

Sample Output #1

1
3
2

Sample Input #2

3 4 2 3
1 3 1

Sample Output #2

1
1
0
2

Sample Input #3

5 6 23 1000
1 2 4 2 3

Sample Output #3

1
25
25
577
274
578

Notes/Hints

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(s_1) = 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$.

Data Size and Constraints

For 60% of the data, $1 \le a_i \le 30$.

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

Note

This problem is translated from COCI2015-2016 CONTEST #5 T6 PODNIZOVI.

见题面 Input 部分

见题面 Output 部分