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.

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.

Ví dụ

Input:

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

Output:

2
6
3