Given n integers, you are asked to answer q queries of the form “What would be the greatest common divisor of ALL the numbers between indices l and r?”

Input

The first line of the input contains two integers n (1 ≤ n ≤ 5000) and q (1 ≤ q ≤ 10).

The next line contains n space-separated integers representing the given array (1 ≤ ≤ ).

The next q lines contain pairs of numbers defining the query ranges (0 ≤ < < n).

Output

The program should print the greatest common divisor for all the numbers between indices l and r inclusive.