P6728 [COCI 2015/2016 #5] PODNIZOVI

Given an array $a_1, a_2, \dots, a_N$ of length $N$. Let $s_1, s_2, \dots, s_q$ be all non-empty subsequences of this array, where $q = 2^n - 1$. About lexicographical order: if the first position where two arrays $A$ and $B$ differ is $i$, and $A_i < B_i$; or $A$ is a strict prefix of $B$ (i.e., they cannot be equal), then $A$ is lexicographically smaller than $B$. We define the hash value of an array consisting of $v_1, v_2, \dots, v_p$ 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, M$ are given integers. For a given integer $K$, find the values of $h(s_1), h(s_2), \dots, h(s_K)$.

The first line contains four integers $N, K, B, M$. The second line contains $N$ integers $a_1, a_2, \dots, a_N$.

Output a total of $K$ lines. The $i$-th line should be the value of $h(s_i)$.

#### Sample Explanation ##### Sample $1$ $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 $2$ $s_1 = [1], s_2 = [1], s_3 = [1, 1], s_4 = [1, 3]$. $h(s1) = 1 \bmod 3 = 1, h(s_2) = 1 \bmod 3 = 1, h(s_3) = (1 \times 2 + 1) \bmod 3 = 0, h(s_4) = (1 \times 2 + 3) \bmod 3 = 2$. #### Constraints For $60\%$ of the testdata, $1 \le a_i \le 30$. For $100\%$ of the testdata, $1 \le N, K, a_i \le 10^5$, $1 \le B, M \le 10^6$, and $K \le 2^N - 1$. #### Notes **Translated from [COCI2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #5](https://hsin.hr/coci/archive/2015_2016/contest5_tasks.pdf) *T6 PODNIZOVI***。 Translated by ChatGPT 5