11879번 - PODNIZOVI 다국어

You are given an array of integers of length N. Let s₁, s₂, ..., 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₁, v₂, ..., v_p as:

h(s) = (v₁ · B^p−1 + v₂ · B^p−2 + ... + v_p−1 · B + v_p) mod M

where B, M are given integers.

Calculate h(s₁), h(s₂), ..., h(s_K) 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 a₁, a₂, a₃, ..., a_N (1 ≤ a_i ≤ 100 000).

In all test cases, it will hold K ≤ 2^N − 1.

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

Clarification of the first example: It holds: s₁ = [1], s₂ = [1, 2], s₃ = [2]. h(s₁) = 1 mod 5 = 1, h(s₂) = (1 + 2) mod 5 = 3, h(s₃) = 2 mod 5 = 2.

Clarification of the second example: It holds: s₁ = [1], s₂ = [1], s₃ = [1, 1], s₄ = [1, 3]. h(s₁) = 1 mod 3 = 1, h(s₂) = 1 mod 3 = 1, h(s₃) = (1 · 2 + 1) mod 3 = 0, h(s₄) = (1 · 2 + 3) mod 3 = 2.