Giáo sư JOI, chuyên gia hàng đầu về lịch sử nước IOI, nhận được một cuốn nhật ký được cho là do một cư dân nước IOI thời cổ đại viết. Để nghiên cứu đời sống ở nước IOI cổ đại từ cuốn nhật ký này, giáo sư quyết định khảo sát các sự kiện được ghi trong đó.

Cuốn nhật ký ghi lại các sự kiện trong $N$ ngày, mỗi ngày đúng một sự kiện. Các sự kiện được phân thành một số loại. Loại sự kiện xảy ra vào ngày thứ $i$ ($1 \le i \le N$) được biểu diễn bằng số nguyên $X_i$. Giá trị $X_i$ càng lớn thì sự kiện được cho là có quy mô càng lớn.

Giáo sư JOI quyết định phân tích cuốn nhật ký theo cách sau.

1. Chọn một số ngày liên tiếp trong $N$ ngày của cuốn nhật ký làm khoảng thời gian phân tích.
2. Định nghĩa độ quan trọng của loại sự kiện $t$ là $t \times (\text{số sự kiện loại }t\text{ trong khoảng thời gian đó})$.
3. Tính độ quan trọng của tất cả các loại sự kiện và tìm giá trị lớn nhất.

Giáo sư JOI giao cho bạn viết chương trình phục vụ việc phân tích. Chương trình cần tìm được độ quan trọng lớn nhất khi được cho một khoảng thời gian phân tích.

Nhiệm vụ

Cho loại sự kiện trong $N$ ngày của cuốn nhật ký và $Q$ truy vấn biểu diễn các khoảng thời gian trong đó, hãy viết chương trình tìm độ quan trọng lớn nhất của các loại sự kiện cho mỗi truy vấn.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên $N,Q$ cách nhau bởi dấu cách, cho biết nhật ký ghi lại $N$ ngày và có $Q$ truy vấn.
• Dòng tiếp theo chứa $N$ số nguyên $X_1,\ldots,X_N$ cách nhau bởi dấu cách. $X_i$ ($1 \le i \le N$) biểu diễn loại sự kiện xảy ra vào ngày thứ $i$.
• Dòng thứ $j$ ($1 \le j \le Q$) trong $Q$ dòng tiếp theo chứa hai số nguyên $A_j,B_j$ ($1 \le A_j \le B_j \le N$) cách nhau bởi dấu cách, cho biết truy vấn thứ $j$ xét khoảng thời gian từ ngày thứ $A_j$ đến ngày thứ $B_j$.

Dữ liệu ra

In ra $Q$ dòng trên đầu ra chuẩn. Dòng thứ $j$ ($1 \le j \le Q$) chứa số nguyên biểu diễn độ quan trọng lớn nhất cho truy vấn thứ $j$.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Nhiệm vụ con

Nhiệm vụ con 1 [5 điểm]

Các điều kiện sau được thỏa mãn.

• $N \le 100$.
• $Q \le 100$.

Nhiệm vụ con 2 [10 điểm]

Các điều kiện sau được thỏa mãn.

• $N \le 5\,000$.
• $Q \le 5\,000$.

Nhiệm vụ con 3 [25 điểm]

• Không tồn tại $i,j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \ne j$) sao cho $A_i \le A_j \le B_j \le B_i$.

Nhiệm vụ con 4 [60 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

Dữ liệu ra 1

9
8
8
16
16

Ghi chú

• Cuốn nhật ký này ghi lại 5 ngày, và các loại sự kiện được ghi là 7, 8 hoặc 9.
• Từ ngày 1 đến ngày 2, độ quan trọng của loại 7 là $7\times0=0$, của loại 8 là $8\times1=8$, và của loại 9 là $9\times1=9$, nên giá trị lớn nhất là 9.
• Từ ngày 3 đến ngày 4, độ quan trọng của loại 7 là $7\times1=7$, của loại 8 là $8\times1=8$, và của loại 9 là $9\times0=0$, nên giá trị lớn nhất là 8.
• Vào ngày 4, độ quan trọng của loại 7 là $7\times0=0$, của loại 8 là $8\times1=8$, và của loại 9 là $9\times0=0$, nên giá trị lớn nhất là 8.
• Từ ngày 1 đến ngày 4, độ quan trọng của loại 7 là $7\times1=7$, của loại 8 là $8\times2=16$, và của loại 9 là $9\times1=9$, nên giá trị lớn nhất là 16.
• Từ ngày 2 đến ngày 4, độ quan trọng của loại 7 là $7\times1=7$, của loại 8 là $8\times2=16$, và của loại 9 là $9\times0=0$, nên giá trị lớn nhất là 16.

Dữ liệu vào 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

Dữ liệu ra 2

27
18
19
19

Ghi chú

Dữ liệu vào này thỏa mãn giới hạn của nhiệm vụ con 3.

Dữ liệu vào 3

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

Dữ liệu ra 3

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15