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