You are given an array of integers of length $N$. Let $s_1,s_2,\dots ,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,\dots ,v_p$ as:

$${\displaystyle h(s)=(v_1\cdot B^{p-1}+v_2\cdot B^{p-2}+\cdots +v_{p-1}\cdot B+v_p)modM}$$ where $B$, $M$ are given integers.

Calculate $h(s_1),h(s_2),\dots ,h(s_K)$ for a given $K$.

Input

The first line contains integers $N,K,B,M$ $(1\le N\le 100000,1\le K\le 100000,1\le B,M\le 1000000)$.

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

In all test cases, it will hold $K\le 2^N-1$.

Output

Output $K$ lines, the $j^{\text{th}}$ line containing $h(s_j)$.

Scoring

In test cases worth 60% of total points, it will additionally hold $1\le a_1,a_2,\dots ,a_N\le 30$.

Sample Input 1

2 3 1 5
1 2

Sample Output 1

1
3
2

Explanation for Sample 1

It holds: $s_1=[1]$, $s_2=[1,2]$, $s_3=[2]$. $h(s_1)=1mod5=1$, $h(s_2)=(1+2)mod5=3$, $h(s_3)=2mod5=2$.

Sample Input 2

3 4 2 3
1 3 1

Sample Output 2

1
1
0
2

Explanation for Sample 2

It holds: $s_1=[1]$, $s_2=[1]$, $s_3=[1,1]$, $s_4=[1,3]$. $h(s_1)=1mod3=1$, $h(s_2)=1mod3=1$, $h(s_3)=(1\cdot 2+1)mod3=0$, $h(s_4)=(1\cdot 2+3)mod3=2$.

Sample Input 3

5 6 23 1000
1 2 4 2 3

Sample Output 3

1
25
25
577
274
578