是的，题目名称中没有拼写错误。

Monocarp 是一个极其古怪的人：他能从购买物品中获得快乐，即使他卖出这些物品的价格比他买入时花的钱还要少。每次 Monocarp 购买一件物品，他就会获得 $1$ 单位的快乐。

有 $n$ 种物品，每种物品由两个整数 $b_i$ 和 $s_i$（$b_i > s_i$）来表示。最初，Monocarp 拥有一定数量的金币。他可以执行以下操作：

• 如果他拥有至少 $b_i$ 个金币，他可以购买一件第 $i$ 种物品，花费 $b_i$ 个金币。你可以认为每种物品的库存是无限的；
• 如果他拥有至少一件尚未售出的第 $i$ 种物品，他可以将其卖出，获得 $s_i$ 个金币。

你需要处理 $q$ 次询问。在第 $j$ 次询问中，你会得到一个整数 $k_j$，你需要计算如果 Monocarp 最初拥有 $k_j$ 个金币，他最多能获得多少单位的快乐。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^4$；$1 \le q \le 10^6$）。

第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$2 \le b_i \le 10^{14}$）。

第三行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \le s_i < b_i$）。

第四行包含三个整数 $x, y, z$（$1 \le x, y, z \le 10^{14}$）。

询问序列按如下方式生成：

• 令 $a_0 = x$，$M = 10^{14} + 31$，当 $j > 0$ 时，$a_j = (a_{j-1} \cdot y + z) \bmod M$；
• 然后，令 $c_0 = 0$，$c_j$ 为第 $j$ 次询问的答案，其中 $j \in [1, q]$；
• 最后，令 $k_j = (a_j + c_{j-1}) \bmod 10^{14}$，其中 $j \in [1, q]$。

输出格式

输出一个整数，即 $c_1 \oplus c_2 \oplus \dots \oplus c_q$，其中 $c_j$ 是第 $j$ 次询问的答案，$\oplus$ 表示按位异或（XOR）运算。

样例

输入样例 1

4 6
10 3 6 7
8 1 3 4
2 1 4

输出样例 1

7

输入样例 2

7 10
5 8 11 9 10 12 4
2 6 9 8 1 11 1
13 1234567891011 37

输出样例 2

16313242560751

说明

在第一个样例中，询问依次为 $6, 12, 19, 27, 35, 43$。它们的答案分别为 $2, 5, 9, 13, 17, 21$。