题目详情 - 小M的区间公约数 - 南阳理工学院OJ

ID: 931

远端评测题

1000ms

128MiB

难度: (无)

上传者:

小M对最大公约数已经很熟悉了，今天突发奇想，她想知道区间最大的公约数。两个数a，b，然后有n组询问，每组询问[L,R]，输出[L,R]区间中a，b最大的公约数，没有输出-1。

Input

第一行输入a，b， (1 ≤ a, b ≤ 10^9)
第二行输入n，(1 ≤ n ≤ 10^4)
然后接下来n行，每行[L,R]。(1 ≤ L ≤ R ≤ 10^9)

Output

输出每次询问的结果。

Sample Input

Sample Output

3
-1
9

HINT

Source