Tý có mảng \(A\) gồm N số nguyên. Với mỗi câu hỏi, cho ba số \(l, r\) và k. Bạn cần tìm phần tử có giá trị nhỏ thứ k nếu ta chỉ xét các phần tử trong khoảng từ chỉ số l đến chỉ số \(r\) và sắp xếp chúng tăng dần.

Ví dụ

Input:

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

Output:

2
6
3

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa \(N\) và Q (\(1 \le N, Q \le 5 \cdot 10^4\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(-10^9 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số \(l, r, k\) (\(1 \le l \le r \le N, 1 \le k \le r -l + 1\)).

Định dạng đầu ra

• In ra giá trị nhỏ thứ \(k\) tìm được cho mỗi truy vấn.