考虑集合 $U = \{0, 1, 2, \dots, n - 1\}$ 的所有子集。每个子集 $A = \{a_1, a_2, \dots, a_k\}$ 唯一对应一个整数 $p(A) = \sum_{i=1}^k 2^{a_i}$。设大小为 $n$ 的集合上的函数 $F$ 由一个长度为 $2^n$ 的整数数组 $f$ 定义：值 $F(A)$ 等于 $f[p(A)]$。

给定两个函数 $F$ 和 $G$。你的任务是找到一个函数 $H$，满足：

$$H(A) = \sum_{B \cup C = A} F(B)G(C)$$

输入格式

第一行包含两个整数 $n$ 和 $t$（$1 \le n \le 16$，$1 \le t \le 100$）。这里 $n$ 是集合 $U$ 的大小，$t$ 是测试数据的数量。

第二行包含两个整数 $a$ 和 $b$，每个数在 $1$ 到 $10^9$ 之间。这些数字用于以下伪随机数生成器中：

unsigned int cur = 0; // 无符号 32 位整数
unsigned int nextRand16() {
    cur = cur * a + b; // 在模 2^32 意义下计算
    return cur / 65536; // 0 到 2^16 - 1 之间的整数
}

测试数据是连续生成的。对于每个测试数据，首先你必须按照数组下标递增的顺序生成数组 $f$ 的元素（即 $F$ 的值），然后以相同的顺序生成数组 $g$ 的元素（即 $G$ 的值）。每个元素都是通过调用函数 nextRand16() 生成的。

输出格式

对于每个测试数据，在单独的一行中输出一个整数：

$$\left(\sum_{A} H(A) \cdot (p(A) + 1)\right) \bmod 2^{32}$$

样例

输入样例 1

3 2
30 239017

输出样例 1

2723387430
3167905008

输入样例 2

16 2
239 17

输出样例 2

551267264
1632349120

说明

第一个样例中的数组如下：

• $f_1$: 3, 113, 3395, 36331, 41370, 61471, 9130, 11774
• $g_1$: 25547, 45526, 55066, 13590, 14501, 41817, 9356, 18543
• $h_1$: 76641, 8167827, 273846333, 5284992017, 1656829263, 11450721456, 3699971823, 14260048942
• $f_2$: 32024, 43238, 51978, 52034, 53714, 38578, 43250, 52338
• $g_2$: 62834, 50034, 59250, 8050, 44914, 36722, 53106, 20338
• $h_2$: 2012196016, 6482475400, 8243104152, 15561662464, 7225902008, 16869349792, 22350138288, 44342816072