COCI '15 Contest 5 #6 Podnizovi

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem types

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

Comments

There are no comments at the moment.