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} + \dots + v_{p-1} \cdot B + v_p) \bmod M$$ 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 100\,000, 1 \le K \le 100\,000, 1 \le B, M \le 1\,000\,000)~.

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

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) = 1 \bmod 5 = 1~, ~h(s_2) = (1+2) \bmod 5 = 3~, ~h(s_3) = 2 \bmod 5 = 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) = 1 \bmod 3 = 1~, ~h(s_2) = 1 \bmod 3 = 1~, ~h(s_3) = (1 \cdot 2+1) \bmod 3 = 0~, ~h(s_4) = (1 \cdot 2+3) \bmod 3 = 2~.

Sample Input 3

5 6 23 1000
1 2 4 2 3

Sample Output 3

1
25
25
577
274
578