Sau khi đậu vào lớp 10 chuyên Tin, Cường được gia đình tặng một hộp quà. Hộp quà gồm \(n\) món quà, món quà thứ \(i\) có giá trị \(a_i\) (\(a_i \le 10^9,\; a_i \ne a_j\) với \(i \ne j\); \(1 \le i \le n\)).
Nhưng để nhận được hộp quà, Cường phải giải đáp được \(Q\) câu hỏi. Câu hỏi thứ \(k\) (\(1 \le k \le Q\)) chứa 3 tham số \(x,y,z\):

• Nếu \(x = 0\): Cường cần đưa ra tổng giá trị của \(z\) món quà có giá trị nhỏ nhất trong \(y\) món quà có giá trị nhỏ nhất.
• Nếu \(x = 1\): Cường cần đưa ra tổng giá trị của \(z\) món quà có giá trị lớn nhất trong \(y\) món quà có giá trị nhỏ nhất.

Yêu cầu: Hãy giúp Cường trả lời các câu hỏi trên.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương \(n, Q\) (\(1 \le n, Q \le 10^5\));
• Dòng thứ hai gồm \(n\) số nguyên \(a_i\) (\(1 \le i \le n\));
• \(Q\) dòng sau, mỗi dòng gồm 3 số nguyên \(x,y,z\) (\(0 \le x \le 1;\; 1 \le z \le y \le n\)).

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra

Với mỗi câu hỏi in kết quả trên một dòng — một số nguyên là tổng theo yêu cầu của câu hỏi.

Ví dụ

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

11
6
7

Phân nhóm