Cho dãy gồm \(N\) số nguyên dương tăng dần.

Có q truy vấn, truy vấn thứ \(i\) có dạng \((k_i, x_i, u_i)\):

• Nếu \(k_i = 0\), cần đưa ra tổng của \(u_i\) số bé nhất trong \(x_i\) số đầu tiên.
• Nếu \(k_i = 1\), cần đưa ra tổng của ui số lớn nhất trong \(x_i\) số đầu tiên.

Dữ liệu:

• Dòng thứ nhất chứa hai số nguyên dương \(n,q (1 ≤ n,q ≤ 100000) \)

• Dòng thứ hai gồm \(n\) số nguyên \(a_i (1 ≤ a_i ≤ 10^9)\)

• \(q\) dòng sau, mỗi dòng gồm \(3\) số nguyên \(k_i, x_i, u_i (1 ≤ u_i ≤ x_i ≤ n)\)

Kết quả:

• Gồm \(q\) dòng, dòng thứ \(i\) trong \(q\) dòng là câu trả lời của truy vấn thứ \(i\).

Sample Input

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

Sample Output

1
10
19

Ràng buộc

- Subtask 1 (50% số test): ~n,m ≤ 1000~.
- Subtask 2 (50% số test): Giới hạn như đề bài