Alice đang chơi một trò chơi, trong đó có một dãy gồm ~n~ số nguyên, Cô ấy được thử thách với một số câu hỏi. Mỗi câu hỏi gồm hai số nguyên ~L~ và ~R~, đại diện cho một đoạn con của dãy.

Nhiệm vụ của Alice là chọn ba số nguyên ~a_i, a_j, a_k~ với chỉ số thỏa mãn điều kiện ~L \le i < j < k \le R~, sao cho tích của ba số đã chọn lớn nhất có thể.

Input

• Dòng đầu tiên có hai số nguyên ~n~ và ~q~ ~(1 \le \frac{n}{3} \le 10^5)~; ~(1 \le q \le 10^5)~.

• Dòng thứ hai có ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^6)~.

• ~q~ dòng tiếp theo, mỗi dòng có hai số nguyên ~L~ và ~R~ ~(1 \le L + 1 < R \le n)~, đại diện cho một câu hỏi.

Output

Gồm ~q~ dòng, một số nguyên duy nhất – giá trị lớn nhất của ~a_i \cdot a_j \cdot a_k~ ứng với ~L, R~ của mỗi câu hỏi.

Scoring

Sample Input 1

5 2
1 -2 3 -4 5
1 3
1 5

Sample Output 1

-6
40