Có ~n~ món quà có giá trị đôi một khác nhau. Mỗi câu hỏi gồm ~x,y,z~ và luôn xét tập ~S~ gồm ~y~ món quà có giá trị nhỏ nhất trong tất cả món quà.

Nếu ~x=0~, cần tính tổng ~z~ món quà nhỏ nhất trong ~S~. Nếu ~x=1~, cần tính tổng ~z~ món quà lớn nhất trong ~S~.

Input

Dòng đầu chứa ~n,Q~ ~(1 \le n,Q \le 10^5)~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ đôi một khác nhau.

~Q~ dòng tiếp theo, mỗi dòng chứa ~x,y,z~ ~(0 \le x \le 1, 1 \le z \le y \le n)~.

Output

Với mỗi câu hỏi, in ra tổng giá trị thỏa mãn trên một dòng.

Subtask

• Có 50% số test có ~n,Q \le 10^3~, ~a_i \le 10^6~.
• Có 50% số test còn lại không có ràng buộc bổ sung.

Ví dụ

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

11
6
7