[EER2] 相同的数字

每天早上在黑板上会写有 $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}$。 | 测试点编号 | 分值 | $n\leq$ | $a_i\leq$ | $T=$ | $q\leq$ |特殊性质| | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $100$ | $100$ | $0$ | $5$ | 所有 $a_i$ 都是质数，$c_1, c_2\leq 10^4$| | $2$ | $10$ | $10^5$ | $10^5$ | $0$ | $5$ | | | $3$ | $25$ | $10^5$ | $10^7$ | $0$ | $5$ | | | $4$ | $10$ | $10^5$ | $10^7$ | $1$ | $5$ | 所有 $a_i$ 都是质数|| | $5$ | $20$ | $10^5$ | $10^7$ | $0$ | $10^5$ | | | $6$ | $22$ | $10^5$ | $10^7$ | $1$ | $10^6$ | | |$7$ | $\color{red}3$ | $10^5$ | $10^7$ | $1$ | $10^6$ | $\color{red}{时限}$ $\color{red}{700ms}$ |