There are $10^{16}$ cities, labeled $1, 2, \dots, 10^{16}$.
For distinct cities $i, j$, there is a bidirectional road between city $i$ and city $j$ if and only if $\operatorname{lcm}(i, j) = A \cdot \gcd(i, j) + B$.
Answer $Q$ queries.
In the $i$-th query, an integer $x_i$ is given. Output the bitwise XOR of the labels of all cities that are reachable from city $x_i$ by traversing zero or more roads.
Input
The first line contains integers $A, B$ in this order, separated by spaces. ($1 \le A, B \le 10^8$)
The second line contains an integer $Q$. ($1 \le Q \le 10^5$)
Each of the following $Q$ lines contains an integer $x_i$ for the $i$-th query. ($1 \le x_i \le 10^{16}$)
Output
Print $Q$ lines.
On the $i$-th line ($1 \le i \le Q$), output the answer to the $i$-th query.
Examples
Sample Input 1
3 28 4 20 26 7 28
Sample Output 1
28 26 54 108
Sample Input 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Sample Output 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Note
For the first example, the existence of a road between cities $i, j$ is equivalent to $\operatorname{lcm}(i, j) = 3 \cdot \gcd(i, j) + 28$.
- For the first query, the cities reachable from city $20$ are $8, 20$.
- For the second query, the only city reachable from city $26$ is $26$.
- For the third query, the cities reachable from city $7$ are $7, 49$.
- For the fourth query, the cities reachable from city $28$ are $28, 112$.
The bitwise XOR $x \oplus y$ of non-negative integers $x, y$ is defined as follows.
- In the binary representation of $x \oplus y$, the digit at the $2^k$ ($k \ge 0$) place is $1$ if and only if exactly one of the digits at the $2^k$ place in the binary representations of $x$ and $y$ is $1$; otherwise, it is $0$.
For example, $3 \oplus 5 = 6$ (in binary, $011 \oplus 101 = 110$).