The author has used up all the creative skills on previous problems, so Anton won't be tortured in this statement. He will just give you an interesting problem.
You are given an array consisting of integers. You are also given queries . For each query, find the maximum value of over all pairs (), where
;
--- the sum of all numbers in the segment ;
--- the greatest common divisor of all numbers in the segment .
The greatest common divisor of two numbers and is the largest positive integer that divides both and .
The greatest common divisor of a set of numbers is the largest positive integer that divides all elements of the set.
输入格式
The first line contains two integers , () --- the number of elements in the array and the number of queries, respectively.
The second line contains integers () --- the description of the array.
Each of the next lines contains two integers , () --- the description of the queries.
输出格式
Print integers --- the answers to the queries.
样例
样例输入 1
3 2
3 3 2
1 3
2 3
样例输出 1
18
9
样例输入 2
8 6
2 4 8 8 8 2 4 16
1 8
2 5
3 4
2 4
7 7
3 6
样例输出 2
256
192
128
128
16
192
数据范围与提示
In the first example, there are following segments:
