I. Max GCD
time limit per test
4 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$.

We define the value of an interval $$$[l,r]$$$ as $$$$$$\max_{\substack{l\le i \lt j \lt k\le r\\j-i\le k-j}}\gcd(a_i,a_j,a_k).$$$$$$ If $$$r-l\le 1$$$, the value is $$$0$$$.

There will be $$$q$$$ queries. In each query, you need to find the value of a particular interval.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3\le n \le 1.5 \times 10^5$$$, $$$1\le q \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots ,a_n$$$ ($$$1\le a_i \le 10^6$$$).

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\le l \le r \le n$$$).

Output

For each query, output one line, an integer, the value of the interval.

Example
Input
8 8
8 24 4 6 6 7 3 3
1 5
2 6
3 7
5 8
4 8
1 3
2 5
3 8
Output
4
2
3
1
3
4
2
3