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 (ki, xi, ui):

• Nếu ki = 0, cần đưa ra tổng của ui số bé nhất trong xi số đầu tiên.
• Nếu ki = 1, cần đưa ra tổng của ui số lớn nhất trong xi 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 ki, xi, ui (1 ≤ ui ≤ xi ≤ 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