Modified GCD#11260
Find the greatest common divisor between two integers and that is in a given range from to (inclusive), i.e. low \le d \le high. It is possible that there is no common divisor in the given range.
You will be given the two integers and , then queries. Each query is a range from to and you have to answer each query.
The first line contains two integers and b~(1 \le a, b \le 10^9). The second line contains the number of queries n~(1 \le n \le 10^4). Then lines follow, each line contains one query consisting of two integers and high~(1 \le low \le high \le 10^9).
Print lines. The -th of them should contain the result of the -th query. If there is no common divisor in the given range for the query, print .
Example 1