题目描述

给出两个正整数 $X$ 和 $Y$，求 $X$ 和 $Y$ 的最大公约数，奶牛可以轻松解决这个问题。
农夫 Farmer John 决定改一改题目去考验奶牛。农夫决定询问奶牛 $Q$ 个问题，每个问题的格式是这样的：
农夫给定两个正整数 $a$ 和 $b$（保证 $a \le b$），然后农夫询问奶牛：在 $a$ 至 $b$ 的范围内，有没有哪个整数既是 $X$ 的约数同时又是 $Y$ 的约数？如果有，输出最大的那个；如果没有，输出 $-1$。

输入格式

第一行，两个正整数 $X$ 和 $Y$。
第二行，一个整数 $Q$。
接下来 $Q$ 行，每行两个正整数 $a$ 和 $b$，保证 $a \le b$。

输出格式

$Q$ 行，每行一个整数，对应每个问题的答案。

样例

200 120
3
9 40
25 35
10 15

40
-1
10

样例解释

• 第一个问题：在 $9$ 至 $40$ 的范围内，既是 $200$ 的约数同时又是 $120$ 的约数的有 $10,20,40$，最大的是 $40$，输出 $40$。
• 第二个问题：在 $25$ 至 $35$ 的范围内，没有公共约数，输出 $-1$。
• 第三个问题：在 $10$ 至 $15$ 的范围内，只有 $10$ 是公共约数，输出 $10$。

10 10
2
1 6
5 5

5
5

样例解释

• 第一个问题：在 $1$ 至 $6$ 的范围内，$10$ 的约数有 $1,2,5,10$，公共约数即 $10$ 的约数，最大的是 $5$，输出 $5$。
• 第二个问题：在 $5$ 至 $5$ 的范围内，只有 $5$，输出 $5$。

数据范围

• 对于 $40\%$ 的数据：$1 \le X, Y \le 100$，$1 \le Q \le 100$，$1 \le a \le b \le 100$。
• 对于 $100\%$ 的数据：$1 \le X, Y \le 10^9$，$1 \le Q \le 30000$，$1 \le a \le b \le 10^9$。