跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0943. Modified GCD

  • ID: 949
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:进阶
  • 上传者:
  • 二分
  • 数论
  • 算法思想
  • 数学
  • 进阶
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Modified GCD

题目描述

C. Modified GCD
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers.

A common divisor for two positive numbers is a number which both numbers are divisible by.

But your teacher wants to give you a harder task, in this task you have to find the greatest common divisor d between two integers a and b that is in a given range from low to high (inclusive), i.e. low≤d≤high. It is possible that there is no common divisor in the given range.

You will be given the two integers a and b, then n queries. Each query is a range from low to high and you have to answer each query.

Input

The first line contains two integers a and b, the two integers as described above (1≤a,b≤109). The second line contains one integer n, the number of queries (1≤n≤104). Then n lines follow, each line contains one query consisting of two integers, low and high (1≤low≤high≤109).

Output

Print n lines. The i-th of them should contain the result of the i-th query in the input. If there is no common divisor in the given range for any query, you should print -1 as a result for this query.

Examples
Input
9 27
3
1 5
10 11
9 11
Output
3
-1
9

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 381 题。保留原作者与原赛事署名。