Existen $10^{16}$ ciudades, etiquetadas como $1, 2, \dots, 10^{16}$.
Para ciudades distintas $i, j$, existe una carretera bidireccional entre la ciudad $i$ y la ciudad $j$ si y solo si $\text{lcm}(i, j) = A \cdot \text{gcd}(i, j) + B$.
Responda $Q$ consultas.
En la $i$-ésima consulta, se da un entero $x_i$. Imprima el XOR bit a bit de las etiquetas de todas las ciudades que son alcanzables desde la ciudad $x_i$ recorriendo cero o más carreteras.
Entrada
La primera línea contiene los enteros $A, B$ en este orden, separados por espacios. ($1 \le A, B \le 10^8$)
La segunda línea contiene un entero $Q$. ($1 \le Q \le 10^5$)
Cada una de las siguientes $Q$ líneas contiene un entero $x_i$ para la $i$-ésima consulta. ($1 \le x_i \le 10^{16}$)
Salida
Imprima $Q$ líneas.
En la $i$-ésima línea ($1 \le i \le Q$), imprima la respuesta a la $i$-ésima consulta.
Ejemplos
Entrada 1
3 28 4 20 26 7 28
Salida 1
28 26 54 108
Entrada 2
81781525 3945925 10 53907475 6160906250298067 3007621769603801 134161450 23675550 4034161385146811 2151358558435 12908151350610 112647860153451 9491287293575
Salida 2
53908389 6160906250298067 3007621769603801 9491260218029 2151369618045 4034161385146811 2151369618045 332851610359999 112647860153451 9491260218029
Nota
Para el primer ejemplo, la existencia de una carretera entre las ciudades $i, j$ es equivalente a $\text{lcm}(i, j) = 3 \cdot \text{gcd}(i, j) + 28$.
- Para la primera consulta, las ciudades alcanzables desde la ciudad 20 son 8, 20.
- Para la segunda consulta, la única ciudad alcanzable desde la ciudad 26 es 26.
- Para la tercera consulta, las ciudades alcanzables desde la ciudad 7 son 7, 49.
- Para la cuarta consulta, las ciudades alcanzables desde la ciudad 28 son 28, 112.
El XOR bit a bit $x \oplus y$ de enteros no negativos $x, y$ se define de la siguiente manera:
- En la representación binaria de $x \oplus y$, el dígito en la posición $2^k$ ($k \ge 0$) es 1 si y solo si exactamente uno de los dígitos en la posición $2^k$ en las representaciones binarias de $x$ e $y$ es 1; de lo contrario, es 0.
Por ejemplo, $3 \oplus 5 = 6$ (en binario, $011 \oplus 101 = 110$).