Description

Every morning, $n$ fixed numbers are written on the blackboard, but they are too messy, so every night the rabbit wants to make them become the same number.

There are two operations:

• Choose an index $k$ and replace $a_k$ with $a_k+1$. Each operation costs $c_1$ time.

• Choose an index $k$ and replace $a_k$ with the smallest prime that is greater than $a_k$. Each operation costs $c_2$ time.

The rabbit is lazy, so he does not want to spend too much time. You need to help him compute the minimum time to make all numbers equal.

There are $q$ days in total. The rabbit’s state is different each day, so each day has different $c_1$ and $c_2$. But the numbers on the blackboard do not change.

The time spent on the first day will of course affect the state of the second day. The real cost each day is $c_1 = c'_1\oplus (T \times (lastans \bmod 2^{17}))$, $c_2 = c'_2 \oplus (T\times (lastans \bmod 2^{17}))$. Here $\oplus$ is the $\operatorname{xor}$ operation, and $lastans$ is the previous answer. Initially, $lastans = 0$.

Input Format

The first line contains three integers $n, q, T$, representing the number of numbers on the blackboard, the total number of days, and a parameter.

The second line contains $n$ integers $a_i$, representing the numbers on the blackboard.

The next $q$ lines each contain two integers $c'_1, c'_2$, representing the parameters of the operation costs for that day.

Output Format

Output $q$ lines. Each line contains one integer, representing the minimum time for that day.

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

Hint

For $100\%$ of the testdata, $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}$.

Translated by ChatGPT 5