给你一个长度为 $N$ 的整数数组。设 $s_1, s_2, \dots, s_q$ 是该数组所有非空子序列按字典序排序后得到的数组。数组的子序列是指通过从原数组中删除零个或多个元素而得到的数组。注意，某些子序列可能会相同，且满足 $q = 2^N - 1$。

如果 $A_i < B_i$（其中 $i$ 是两个数组出现不同的第一个位置），或者 $A$ 是 $B$ 的严格前缀，则称数组 $A$ 在字典序上小于数组 $B$。

我们定义一个由值 $v_1, v_2, \dots, v_p$ 组成的数组的哈希值为：

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

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

对于给定的 $K$，计算 $h(s_1), h(s_2), \dots, h(s_K)$。

输入格式

第一行包含整数 $N, K, B, M$（$1 \le N \le 100\,000$，$1 \le K \le 100\,000$，$1 \le B, M \le 1\,000\,000$）。

第二行包含整数 $a_1, a_2, a_3, \dots, a_N$（$1 \le a_i \le 100\,000$）。

在所有测试数据中，均满足 $K \le 2^N - 1$。

输出格式

输出 $K$ 行，第 $j$ 行包含 $h(s_j)$。

子任务

在占总分 60% 的测试数据中，还满足 $1 \le a_1, a_2, \dots, a_N \le 30$。

样例

输入样例 1

2 3 1 5
1 2

输出样例 1

1
3
2

输入样例 2

3 4 2 3
1 3 1

输出样例 2

1
1
0
2

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