Một ngày nọ, Doraemon muốn Nobita chứng minh khả năng toán học của mình với Shizuka. Mèo máy cố tình tạo ra một câu đố khó và tin chắc rằng Nobita sẽ giải được, từ đó lấy lòng Shizuka. Doraemon ghi ra tờ giấy trắng một dãy ~N~ số nguyên dương tăng dần.

Tiếp theo đó, Shizuka đưa cho Nobita ~Q~ câu hỏi. Câu hỏi thứ ~i~ chứa ~3~ giá trị ~type_i, x_i, k_i~.

• Nếu ~type_i = 0~, Nobita cần đưa ra tổng của ~k_i~ số bé nhất trong ~x_i~ số đầu tiên.

• Nếu ~type_i = 1~, Nobita cần đưa ra tổng của ~k_i~ số lớn nhất trong ~x_i~ số đầu tiên.

Bạn hãy giúp Nobita trả lời các câu hỏi để gây ấn tượng với Shizuka nhé.

Dữ liệu

• 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_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^9)~ — dãy số tăng dần mà Doraemon đã ghi.

• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên ~type_i, x_i, k_i~ ~(0 \le type_i \le 1,\ 1 \le k_i \le x_i \le n)~.

Kết quả

Với mỗi câu hỏi, in ra câu trả lời trên một dòng.

Ví dụ

Sample Input

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

Sample Output

1
10
19

Chấm điểm

• Subtask 1 (50% số test): ~n, q \le 10^3~.

• Subtask 2 (50% số test): Giới hạn như đề bài.