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.