← 返回题目列表

Codeforces · 75/C

C. 修改后的 GCD

中文机器翻译题面 查看原题

嗯,这是另一个数学课堂任务。在数学中,GCD是最大公约数,计算两个正整数之间的GCD是一件容易的事。

两个正数的公约数是两个数都可以被整除的数。

但是你的老师想给你一个更难的任务,在这个任务中你必须找到两个整数a和b之间的最大公约数d,并且这个最大公约数d在给定范围从低到高(含),即低≤d≤高。给定范围内可能没有公约数。

你将得到两个整数a和b,然后是n个查询。每个查询都是从低到高的范围,您必须回答每个查询。

输入

第一行包含两个整数 a 和 b,这两个整数如上所述 (1 ≤ a, b ≤ 109)。第二行包含一个整数n,即查询次数(1 ≤ n ≤ 104)。接下来是 n 行,每行包含一个由两个整数 low 和 high (1 ≤ low ≤ high ≤ 109) 组成的查询。

输出

打印 n 行。其中第 i 个应该包含输入中第 i 个查询的结果。如果任何查询的给定范围内都没有公约数,则应打印 -1 作为该查询的结果。

示例

输入 #1

9 27
3
1 5
10 11
9 11

输出 #1

3
-1
9