GCD on a range of numbers

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.

Examples

Input
Output
8 4 12 24 198 64 9 8 4 100 0 1 1 2 1 4 5 7
12 6 1 4
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue