문제

1 second, 256 MB, 160 points You are given an array of integers of length N. Let s1, s2, ..., sq 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 = 2N −1. An array A is lexicographically smaller than array B if Ai < Bi 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 v1, v2, ..., vp as: h(s) = (v1 · Bp−1 + v2 · Bp−2 + ... + vp−1 · B + vp) mod M where B, M are given integers. Calculate h(s1), h(s2), ..., h(sK) for a given K.

입력

The first line contains integers N, K, B, M (1 ⩽N ⩽100 000, 1 ⩽K ⩽100 000, 1 ⩽B, M ⩽ 1 000 000). The second line contains integers a1, a2, a3, ..., aN (1 ⩽ai ⩽100 000). In all test cases, it will hold K ⩽2N −1.

출력

Output K lines, the jth line containing h(sj).

예제 입력 1

2 3 1 5
1 2

예제 출력 1

1
3
2

예제 입력 2

3 4 2 3
1 3 1

예제 출력 2

1
1
0
2

예제 입력 3

5 6 23 1000
1 2 4 2 3

예제 출력 3

1
25
25
577
274
578