Lexicographically Sorted Subsequence Hashes

Given an array \(a_1,a_2,\dots,a_N\) of length \(N\). Consider all non-empty subsequences of the array; there are \(q=2^N-1\) such subsequences. We define the lexicographic order between two subsequences \(A\) and \(B\) as follows: if the first position where they differ is \(i\) and \(A_i .

For any subsequence \(s = [v_1, v_2,\dots,v_p]\), its hash value 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\), output the hash values \(h(s_1),h(s_2),\dots,h(s_K)\) for the first \(K\) subsequences in lexicographic order.

inputFormat

The first line contains four integers \(N\), \(K\), \(B\), and \(M\). The second line contains \(N\) integers representing the array \(a_1,a_2,\dots,a_N\).

outputFormat

Output the hash values of the first \(K\) lexicographically smallest non-empty subsequences. The values should be printed in order, separated by spaces.

sample

2 3 10 1000
1 2

1 12 2