Little Desprado2 几天前刚学会如何计算两个正整数的最大公约数（GCD）。欧几里得算法是历史上最著名的算法之一，它以两个正整数 $x, y$ 作为输入，递归调用自身，并最终返回它们的 GCD：

• 如果 $y \neq 0$，返回 $\gcd(y, x \bmod y)$；
• 否则，返回 $x$。

Little Desprado2 觉得这还不够有趣，因为每个人都知道它。现在，他想通过生成一些无穷序列来展示 GCD 的一些性质。他有两个正整数 $P$ 和 $Q$，且满足 $Q|P$。这里 $a|b$ 表示 $a$ 是 $b$ 的因数，即 $b \bmod a = 0$。他有 $k$ 组正整数候选对 $\{(a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)\}$，用于生成 $k$ 个无穷序列，其中第 $i$ 个序列 $\{x_{i,0}, x_{i,1}, x_{i,2}, \dots\}$ 由以下规则生成：

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

他认为一个无穷序列 $\{x_0, x_1, x_2, \dots\}$ 是 demonstrational 的，当且仅当存在两个整数 $u$ 和 $v$ ($0 \le v < u$) 使得 $\gcd(x_u - x_v, P) = Q$。这里 $\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数。

对于每一个无穷序列，Little Desprado2 想让你告诉他该序列是否是 demonstrational 的。

输入格式

第一行包含三个整数 $P, Q, k$ ($1 \le P \le 2^{32} - 1, 1 \le Q \le 2^{20}, 1 \le k \le 200$)。保证满足 $Q|P$。

接下来 $k$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 2^{64} - 1$)，表示第 $i$ 组数字。

输出格式

输出一个长度为 $k$ 的 0/1 字符串。如果第 $i$ 个无穷序列是 demonstrational 的，则第 $i$ 个字符为 1，否则为 0。

样例

样例输入 1

15 5 5
1 1
1 2
2 4
4 8
8 16

样例输出 1

11010

样例输入 2

998244352 1048576 3
2022 924
12345678 1234567
23333333 6666666

样例输出 2

001

说明

在第一个样例中：

• 第一个无穷序列 $\{x_{1,0}, x_{1,1}, x_{1,2}, \dots\}$ 是 $\{1, 2, 5, 26, \dots\}$，因此存在 $u = 3, v = 0$ 满足 $\gcd(x_u - x_v, P) = \gcd(26 - 1, 15) = 5 = Q$。因此，第一个序列是 demonstrational 的。
• 第二个无穷序列是 demonstrational 的，其中一个解是 $u = 2, v = 0$。
• 第四个无穷序列也是 demonstrational 的，其中一个解是 $u = 2, v = 1$。
• 可以证明第三个和第五个无穷序列不是 demonstrational 的。