Recently while playing cricket, vampire got frustrated and went on a mission to “Networking Land” to find peace. There, he came across a number of islands arranged in a row.

Each island had a holy number associated with it. The holy number of a range of consecutive islands was the maximum number that could divide holy numbers of all of the islands in that range. Vampire has a number of queries where he needs to find the holy number of some range of islands. Help him do so.

Input

The first line contains n and q, the number of islands and the number of queries. the next line contains n integers denoting the holy number of all the islands. this is followed by q lines, each line contains 2 integers l, r. You need to output the holy value of the range l, r.

Output

The output should contain q lines, each denoting the answer to each query.

Constraints

q <= 10000

n <= 100000

holy numbers <= 1000000000

Example

Input:
5 5
2 4 6 9 18
1 1
1 3
3 4
3 5
4 5

Output:
2
2
3
3
9