Cho dãy số ~A~ gồm ~N~ số nguyên. Bạn cần trả lời ~Q~ truy vấn như sau: cho hai số nguyên ~l~, ~r~, tìm 3 số nguyên ~i, j, k~ ~(l \leq i < j < k \leq r)~ sao cho tích ~a[i] * a[j] * a[k]~ nhỏ nhất.

Input

Dòng đầu tiên gồm hai số nguyên dương ~N~, ~Q~ ~(1 \leq N, Q \leq 2*10^5)~.

Dòng tiếp theo gồm ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(-10^6 \leq a_i \leq 10^6)~.

~Q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~l, r~ ~(1 \leq l \leq r \leq N, r - l \geq 2)~.

Output

In ra ~Q~ dòng, mỗi dòng gồm một số nguyên là tích cần tìm.

Sample Input 1

7 7
-1 -4 -2 5 -3 -3 4
3 6
1 7
4 7
3 6
3 7
2 7
4 7

Sample Output 1

-18
-80
-60
-18
-60
-80
-60

Sample Input 2

6 6
3 2 3 0 -5 0
2 5
1 6
2 6
1 5
3 6
4 6

Sample Output 2

-30
-45
-30
-45
0
0