Uniform Number Transformation

Every morning, a blackboard displays n fixed numbers. However, they are too unordered, so every evening the rabbit wants to transform them into an identical number by applying some operations. Two operations are allowed:

• Choose an index k and replace \(a_k\) with \(a_k+1\). This operation costs \(c_1\) time.
• Choose an index k and replace \(a_k\) with the smallest prime greater than \(a_k\) (i.e. \(P(a_k)\)). This operation costs \(c_2\) time.

The rabbit is lazy and wants to minimize his total time. You need to help him compute the minimum time required to make all numbers equal.

There are \(q\) days. Since the rabbit’s state is different every day, the cost parameters for each day differ. However, the numbers on the board remain fixed. Note: The time spent on day 1 will affect the state of day 2. Specifically, if the input costs for a day are \(c'_1\) and \(c'_2\), then the real costs for that day are computed as:

[ \begin{aligned} c_1 &= c'_1 \oplus \Bigl(T \times (lastans \bmod 2^{17})\Bigr),\ c_2 &= c'_2 \oplus \Bigl(T \times (lastans \bmod 2^{17})\Bigr), \end{aligned} ]

Here, \(\oplus\) denotes the bitwise XOR operation, and lastans is the answer from the previous day (initially, lastans = 0).

Operation details:

• You are allowed to perform the two operations on any of the numbers arbitrarily many times. Note that when applying the second operation on a number \(x\), it is replaced by the unique value \(P(x)\), which is defined as the smallest prime greater than \(x\).
• For a given number \(a\), a sequence of operations can be described by a series of prime jumps. Let \(v_0=a\) and for any \(r \ge 1\), let \(v_r = P(v_{r-1})\). Then, if you perform exactly \(r\) prime jump operations followed by increments to reach the target \(X\) (with \(X \ge v_r\)), the cost for that element is:

[ \text{cost}(a, X)= \min_{r \ge 0,; v_r \le X} \Bigl{ r,c_2 + (X-v_r),c_1\Bigr}. ]

Your task is to choose a target \(X\) (with the constraint \(X \ge \max\{a_i\}\)) and for each element compute the above cost, summing them up to obtain the total cost. Output the minimum total cost among all possible valid \(X\).

inputFormat

The first line contains three integers: n, q and T.

The second line contains n integers \(a_1, a_2, \ldots, a_n\) — the fixed numbers on the board.

Each of the following q lines contains two integers \(c'_1\) and \(c'_2\) (the preliminary costs for that day). For each day, the actual costs are computed as:

[ \begin{aligned} c_1 &= c'_1 \oplus \Bigl(T \times (lastans \bmod 2^{17})\Bigr),\ c_2 &= c'_2 \oplus \Bigl(T \times (lastans \bmod 2^{17})\Bigr). \end{aligned} ]

Remember that lastans is initially 0 and is updated to the answer of the previous day after processing each query.

outputFormat

For each day, output one line containing the minimum total time needed to transform all numbers into a same number.

sample

3 2 1
2 3 5
1 2
3 4

5
3

</p>