GCD of Subarray Queries

You are given an array of integers and several queries. Each query consists of two integers, (L) and (R), representing the starting and ending positions (1-indexed) of a subarray. For each query, compute the greatest common divisor (GCD) of the subarray elements. The GCD of two numbers, (a) and (b), is given by (\gcd(a, b)). Use the property that (\gcd(a, b, c) = \gcd(\gcd(a, b), c)).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n), the number of elements in the array. The second line contains (n) space-separated integers representing the array elements. The third line contains an integer (q), the number of queries. This is followed by (q) lines where each line contains two integers (L) and (R) (1-indexed) specifying the range of the subarray.

outputFormat

For each query, output the GCD of the subarray from index (L) to (R) (inclusive) on a new line, via standard output (stdout).## sample

5
12 15 18 24 30
3
1 3
2 4
1 5

3
3
3