F. 1e16 Cities
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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\leq A,B \leq 10^8$$$)

The second line contains an integer $$$Q$$$. ($$$1\leq Q\leq 10^5$$$)

Each of the following $$$Q$$$ lines contains an integer $$$x_i$$$ for the $$$i$$$-th query. ($$$1\leq x_i\leq 10^{16}$$$)

Output

Print $$$Q$$$ lines.

On the $$$i$$$-th line $$$(1\leq i\leq Q)$$$, output the answer to the $$$i$$$-th query.

Examples
Input
3 28
4
20
26
7
28
Output
28
26
54
108
Input
81781525 3945925
10
53907475
6160906250298067
3007621769603801
134161450
23675550
4034161385146811
2151358558435
12908151350610
112647860153451
9491287293575
Output
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 \geq 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$$$).