Найдите наибольший общий делитель 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.