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