A1316 | [COCI-2015_2016-contest5]#4 PODNIZOVI

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 6 N 6 100 000, 1 6 K 6 100 000, 1 6 B, M 6 1 000 000).
The second line contains integers a1, a2, a3, ..., aN (1 6 ai 6 100 000).
In all test cases, it will hold K 6 2 N −
1.

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