Найдите наибольший общий делитель $d$ двух целых чисел $a$ и $b$, принадлежащий отрезку целых чисел $[low, high]~(low \le high)$, то есть такой, что $low \le d \le high$. Может получиться, что в заданном отрезке нет общих делителей. Даны два целых числа $a$ и $b$, далее следует $n$ запросов. Каждый запрос --- это некоторый отрезок $[low, high]$. Напишите программу, которая обработает все заданные запросы. \InputFile В первой строке записано два целых числа $a$ и $b~(1 \le a, b \le 10^9)$. Во второй строке содержится количество запросов $n~(1 \le n \le 10^4)$. Далее следует $n$ строк. Каждая строка содержит один запрос --- два целых числа $low$ и $high~(1 \le low \le high \le 10^9)$. \OutputFile Выведите $n$ строк, $i$-ая из которых должна содержать ответ на $i$-ый запрос. Если в данном отрезке общих делителей нет, выведите $-1$.