GCD Subarray Query

You are given an array of n integers and q queries. Each query consists of two integers, l and r (1-indexed), representing the range of a subarray. For each query, you must compute the greatest common divisor (GCD) of all the integers in the subarray from index l to r.

The GCD of two numbers a and b is defined as the largest integer that divides both without leaving a remainder. In mathematical terms, if we denote the GCD of a and b by \(\gcd(a,b)\), then for a range \([l, r]\), you need to compute:

\(\gcd(array[l], array[l+1], \ldots, array[r])\)

It is guaranteed that \(1 \leq l \leq r \leq n\).

inputFormat

The first line of input contains two integers n and q, where n is the number of integers in the array and q is the number of queries.

The second line contains n space-separated integers representing the array elements.

Each of the next q lines contains two space-separated integers l and r, denoting the starting and ending indices (1-indexed) of the subarray for which the GCD must be computed.

outputFormat

For each query, output a single line containing the GCD of the subarray defined by the indices l and r.

## sample

6 3
12 15 18 21 24 27
2 4
1 6
3 5

3
3
3

</p>