嗯,这是另一个数学课堂任务。在数学中,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