D. Demonstrational sequences
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Little Desprado2 learned how to calculate the Greatest Common Divisor (GCD) of two positive numbers a few days ago. One of the most famous algorithm in the history is the Euclidean Algorithm, which takes two positive integers $$$x, y$$$ as input, calls itself recursively, and finally returns the GCD of them:
  • If $$$y \neq 0$$$, return $$$\gcd(y, x \bmod y)$$$;
  • Otherwise, return $$$x$$$.

Little Desprado2 doesn't think it is interesting enough since everybody knows it. Now, he wants demonstrate some properties of the GCD by generating some infinite sequences. He has two positive integers $$$P$$$ and $$$Q$$$, and $$$Q|P$$$ is satisfied. Here $$$a|b$$$ means that $$$a$$$ is a factor of $$$b$$$, that is, $$$b \bmod a = 0$$$. And he has $$$k$$$ candidate pairs of positive numbers $$$\{(a_1,b_1),(a_2,b_2),...,(a_k,b_k)\}$$$ to generate $$$k$$$ infinite sequence, where the $$$i$$$-th sequence $$$\{x_{i,0},\ x_{i,1},\ x_{i,2},\ ...\}$$$ is generated by the following rules:

  • $$$x_{i,0} = a_i$$$
  • $$$x_{i,j}=x_{i,j-1}^2 + b_i$$$ ($$$j \gt 0$$$)

He thinks that an infinite sequence $$$\{x_0,\ x_1,\ x_2,\ ...\}$$$ is demonstrational, if and only if there exists two integers $$$u$$$ and $$$v$$$ ($$$0\le v \lt u$$$) such that $$$\gcd(x_u-x_v, P) = Q$$$. Here $$$\gcd(a,b)$$$ denotes the greatest common divisor of $$$a$$$ and $$$b$$$.

For each infinite sequences, Little Desprado2 wants you to tell him whether it is demonstrational.

Input

The first line contains three integers $$$P, Q, k$$$ ($$$1\le P\le 2^{32}-1$$$, $$$1\le Q\le 2^{20}$$$, $$$1\le k\le 200$$$). It's guaranteed that $$$Q|P$$$ is satisfied.

Then follows $$$k$$$ lines. The $$$i$$$-th line contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1\le a_i,\ b_i\le 2^{64}-1$$$), denoting the $$$i$$$-th pair of numbers.

Output

Print a $$$0/1$$$ string of length $$$k$$$. The $$$i$$$-th character is $$$1$$$ if the $$$i$$$-th infinite sequence is demonstrational, $$$0$$$ otherwise.

Examples

Input
15 5 5
1 1
1 2
2 4
4 8
8 16
Output
11010
Input
998244352 1048576 3
2022 924
12345678 1234567
23333333 6666666
Output
001
Note

In the first example,

  • The first infinite sequence $$$\{x_{1,0}, x_{1,1}, x_{1,2},\dots\}$$$ is $$$\{1,2,5,26, \dots\}$$$, so there is $$$u=3, v=0$$$ satisfied $$$\gcd(x_u-x_v, P)$$$ $$$= \gcd(26-1, 15)$$$ $$$= 5 = Q$$$. Therefore, the first sequence is demonstrational.
  • The second infinite sequence is demonstrational, and one of the solutions is $$$u=2, v=0$$$.
  • The fourth infinite sequence is also demonstrational, and one of the solutions is $$$u=2, v=1$$$.
  • It can be proved that the third and the fifth infinite sequence is not demonstrational.