410042: GYM103931 D Demonstrational sequences

D. Demonstrational sequencestime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard 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>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 < 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.