GCD, Sum, Multiply. What?...
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $$$a$$$ consisting of $$$n$$$ integers. You are also given $$$q$$$ queries $$$[l;r]$$$. For each query, find the maximum value of $$$\operatorname{sum}[tl;tr] \times \operatorname{gcd}[tl;tr]$$$ over all pairs ($$$tl;tr$$$), where

- $$$l \le tl \le tr \le r$$$;
- $$$\operatorname{sum}[tl;tr]$$$ — the sum of all numbers in the segment $$$[tl;tr]$$$;
- $$$\operatorname{gcd}[tl;tr]$$$ — the greatest common divisor of all numbers in the segment $$$[tl;tr]$$$.

The greatest common divisor of two numbers $$$a$$$ and $$$b$$$ is the largest positive integer $$$x$$$ that divides both $$$a$$$ and $$$b$$$.

The greatest common divisor of a set of numbers is the largest positive integer $$$x$$$ that divides all elements of the set.

Input

The first line contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of elements in the array and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 6 \cdot 10^6$$$) — the description of the array.

Each of the next $$$q$$$ lines contains two integers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n$$$) — the description of the queries.

Output

Print $$$q$$$ integers — the answers to the queries.

Scoring

1. ($$$4$$$ points): $$$n \le 3$$$;
2. ($$$8$$$ points): $$$n, q \le 10^3$$$;
3. ($$$5$$$ points): $$$n \le 10^3$$$;
4. ($$$17$$$ points): $$$n, q \le 10^5$$$;
5. ($$$14$$$ points): $$$n \le 10^5$$$;
6. ($$$5$$$ points): $$$a_i \le 20$$$;
7. ($$$7$$$ points): $$$a_i \le 10^3$$$;
8. ($$$16$$$ points): $$$l = 1$$$;
9. ($$$24$$$ points): no additional constraints.

Examples

Input

    3 23 3 21 32 3

Output

    18
    9

Input

    8 62 4 8 8 8 2 4 161 82 53 42 47 73 6

Output

    256
    192
    128
    128
    16
    192

Note

In the first example, there are following segments:

- $$$[1;1]$$$ — $$$\operatorname{sum}[1;1] \times \operatorname{gcd}[1;1]$$$ = $$$3 \times 3$$$ = $$$9$$$;

- $$$[1;2]$$$ — $$$\operatorname{sum}[1;2] \times \operatorname{gcd}[1;2]$$$ = $$$6 \times 3$$$ = $$$18$$$;

- $$$[1;3]$$$ — $$$\operatorname{sum}[1;3] \times \operatorname{gcd}[1;3]$$$ = $$$8 \times 1$$$ = $$$8$$$;

- $$$[2;2]$$$ — $$$\operatorname{sum}[2;2] \times \operatorname{gcd}[2;2]$$$ = $$$3 \times 3$$$ = $$$9$$$;

- $$$[2;3]$$$ — $$$\operatorname{sum}[2;3] \times \operatorname{gcd}[2;3]$$$ = $$$5 \times 1$$$ = $$$5$$$;

- $$$[3;3]$$$ — $$$\operatorname{sum}[3;3] \times \operatorname{gcd}[3;3]$$$ = $$$2 \times 2$$$ = $$$4$$$.