题目描述

给定一个长度为 $N$ 的数组 $a_1,a_2,\dots,a_N$。令 $s_1,s_2,\dots,s_q$ 为这个数组所有的非空子序列，且 $q=2^n-1$。

关于字典序：如果两个数组 $A$ 和 $B$ 的第一个不相同的位置为 $i$，且 $A_i < B_i$；或 $A$ 是 $B$ 的严格前缀（即不能相等），则 $A$ 的字典序小于 $B$。

我们将由 $v_1,v_2,\dots,v_p$ 组成的数组的 hash 值定义为：

$$h(s)=(v_1\times B^{p-1}+v_2\times B^{p-2}+\dots +v_{p-1}\times B+v_p) \bmod M$$

其中 $B,M$ 是给定的整数。

对于给定的整数 $K$，求 $h(s_1),h(s_2),\dots,h(s_K)$ 的值。

输入格式

第一行四个整数 $N,K,B,M$。

第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。

输出格式

输出共 $K$ 行，第 $i$ 行为 $h(s_i)$ 的值。

样例 #1

样例输入 #1

2 3 1 5
1 2

样例输出 #1

1
3
2

样例 #2

样例输入 #2

3 4 2

样例输出 #2

1
1
0
2

样例 #3

样例输入 #3

5 6 23 1000
1 2 4 2 3

样例输出 #3

1
25
25
577
274
578

提示

样例解释

样例 $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$。

样例 $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$。

数据规模与约定

对于 $60\%$ 的数据，$1\le a_i\le 30$；
对于 $100\%$ 的数据，$1\le N,K,a_i\le 10^5$，$1\le B,M\le 10^6$，$K\le 2^N-1$。