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.

INPUT

• 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.

OUTPUT

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.

SAMPLE INPUT 1

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

SAMPLE OUTPUT 1

11
6
7

SUBTASKS