题目描述

每天早上在黑板上会写有 $n$ 个固定的数字，但是这些数字太无序了，所以每天晚上兔子想把他们变成相同的数字。

有两种操作 :

• 选择一个下标 $k$，将 $a_k$ 替换为 $a_k+1$。一次操作花费 $c_1$ 的时间。

• 选择一个下标 $k$，将 $a_k$ 替换为大于 $a_k$ 的最小质数。一次操作花费 $c_2$ 的时间。

兔子很懒，所以他不想花费太多的时间，你需要帮他计算出将所有数变相同的最小时间。

总共会有 $q$ 天。兔子每天的状态不同，所以每一天会有不同的 $c_1$ 和 $c_2$。但是黑板上的数不会变。

第一天花费的时间当然会影响第二天的状态。每天真实的 $c_1 = c'_1\oplus (T \times (lastans \bmod 2^{17}))$，$c_2 = c'_2 \oplus (T\times (lastans \bmod 2^{17}))$。其中 $\oplus$ 为 $\operatorname{xor}$ 运算，$lastans$ 为上一次的答案，最初 $lastans = 0$。

输入格式

第一行三个整数 $n, q, T$，表示黑板上数的个数、总天数和一个参数。

第二行 $n$ 个整数 $a_i$，表示黑板上的数。

接下来 $q$ 行，每行两个整数 $c'_1, c'_2$，表示每天操作花费的参数。

输出格式

共 $q$ 行，每行一个整数，表示一天的最小时间。

5 2 0
3 5 8 14 16
2 3
1 3

41
32

4 2 1
2 3 5 8
1 2
12 9

14
28

提示

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^7$，$0 \leq T \leq 1$，$1 \leq q \leq 10^6$，$1 \leq c_1, c_2, c'_1, c'_2< 2^{17}$。