Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Модифицированный НОД
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Что ж, вот еще одна математическая задача. Как известно, НОД — наибольший общий делитель. Найти НОД двух положительных целых чисел несложно.

Общий делитель двух положительных чисел — это число на которое делятся оба этих числа.

Но Вам дана более сложная задача. Требуется найти наибольший общий делитель d двух целых чисел a и b, принадлежащий отрезку целых чисел [low, high] (low ≤ high), то есть такой, что low ≤ d ≤ high.

Может получиться, что в заданном отрезке нет общих делителей.

Даны два целых числа a и b, далее следует n запросов. Каждый запрос — это некоторый отрезок [low, high]. Напишите программу, которая обработает все заданные запросы.

Входные данные

В первой строке записано два целых числа a и b, описанных выше (1 ≤ a, b ≤ 109). Во второй строке содержится одно целое число n, количество запросов (1 ≤ n ≤ 104). Далее следует n строк. Каждая строка содержит один запрос — два целых числа low и high (1 ≤ low ≤ high ≤ 109).

Выходные данные

Выведите n строк, i-ая из них должна содержать ответ на i-ый запрос из входных данных. Если в данном отрезке общих делителей нет, выводите -1 в качестве ответа на запрос.

Примеры
Входные данные
9 27
3
1 5
10 11
9 11
Выходные данные
3
-1
9