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

输入格式

第一行，两个正整数，X 和 Y。
第二行，一个整数数，Q。
接下来有 Q 行，每行两个正整数：a 和 b，其中保证 a <= b。

输出格式

共 Q 行，每行一个整数，每行对应农夫的一个问题。

输入1

200 120

3

9 40

25 35

10 15

输入1

40

-1

10

【样例1解释】

第一个问题：在9至40的范围内，既是200的约数，同时又是120的约数，共有3个，分别是：10，20，40，在3个之中，40最大，所以输出40。第二个问题：在25至35的范围内，找不到既是200的约数，同时又是120的约数，所以输出-1。第三个问题：在10至15的范围内，既是200的约数，|同时又是120的约数，只有10，所以输出10。

输入2

10 10

2

1 6

5 3

输出2

5 5

【样例2解释】

第一个问题：在1至6的范围内，既是10的约数，同时又是10的约数，有2和5，所以输出5。第二个问题：在5至5的范围内，既是10的约数，同|时又是10的约数，只有5，所以输出5。

1、对于 40%的数据，1<=X<=100，1 <= Y <= 100， 1 <= Q <= 100，1<=a<b<=100 

2、对于 100%的数据，1<=X<=1000000000，1 <= Y <= 1000000000， 1 <= Q <= 30000，1<=a<b<=1000000000