A. An Easy Array Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an array problem.

Given $$$N$$$ numbers, $$$A_1, \dots A_N$$$, answer $$$Q$$$ queries as follows:

Given $$$L, R$$$ where $$$R - L + 1 \geq 4$$$, among all possible $$$L \lt X \lt Y \lt R$$$, maximise $$$A_L \times A_X \times A_Y \times A_R$$$. Output on a single line this maximised value.

Input

The first line contains two space-separated integers, $$$N$$$, the number of numbers, and $$$Q$$$, the number of queries.

The second line contains $$$N$$$ space-separated integers, $$$A_1, A_2, \dots, A_N$$$.

$$$Q$$$ lines follow, the $$$i^{th}$$$ line contains 2 space-separated integers, $$$L_i, R_i$$$, which are the $$$L, R$$$ values for the $$$i^{th}$$$ query.

Output

Output $$$Q$$$ lines, each containing a single integer which is the answer for the $$$i^{th}$$$ query.

Scoring

$$$1 \leq N, Q \leq 5 \times 10^5$$$

$$$-10^4 \leq A_i \leq 10^4$$$

$$$1 \leq L_i \lt L_i+3 \leq R_i \leq N$$$

Examples
Input
7 3
-1 2 1 4 -2 -3 2
1 7
2 7
1 6
Output
24
24
24
Input
10 10
564 7167 -4069 -3244 579 199 -9838 2913 9796 4734
2 6
1 6
2 7
1 7
4 10
1 9
5 10
1 7
4 9
5 9
Output
18826041697788
1481496793296
166115621837646
161812108318536
1480010149948608
221168049823968
78216085767528
161812108318536
910703330545056
3287917420308