Năm 2036, bạn là kỹ sư trưởng của trạm vũ trụ Clue. Trạm sở hữu một dải pin năng lượng gồm ~n~ lõi được xếp thành một hàng ngang, đánh số từ ~1~ đến ~n~. Mỗi lõi mang một mức năng lượng là một số nguyên ~a_i~ (có thể mang giá trị âm do chứa phản vật chất).

Để kích hoạt một phản ứng nhiệt hạch tối đa, hệ thống yêu cầu chọn ra chính xác 3 lõi năng lượng khác nhau. Năng lượng sinh ra từ phản ứng sẽ bằng tích mức năng lượng của 3 lõi được chọn.

Trong quá trình kiểm tra định kỳ, hệ thống đưa ra ~q~ truy vấn. Mỗi truy vấn cung cấp một đoạn giới hạn từ chỉ số ~L~ đến ~R~. Nhiệm vụ của bạn là chọn ra 3 chỉ số ~i, j, k~ thỏa mãn ~L \le i < j < k \le R~ sao cho tổng năng lượng sinh ra ~a_i \cdot a_j \cdot a_k~ là lớn nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ (~3 \le n \le 2 \cdot 10^5~; ~1 \le q \le 5 \cdot 10^5~).
• Dòng thứ hai chứa ~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 chứa hai số nguyên dương ~L~ và ~R~ (~1 \le L \le R - 2 < R \le n~), đại diện cho một truy vấn.

Output

~q~ dòng, mỗi dòng là mức năng lượng lớn nhất có thể đạt được ứng với từng truy vấn.

Sample Input

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

Sample Output

60
72