Tèo có một dãy số và cần trả lời \(Q\) truy vấn. Mỗi truy vấn cho ba số \(l, r, k\), yêu cầu tìm phần tử nhỏ thứ \(k\) trong đoạn \([l, r]\).

Ràng buộc

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

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

Định dạng đầu ra

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

Ví dụ

Input:

6 4
5 2 8 2 7 4
1 5 2
2 6 3
3 5 1
1 6 4

Output:

2
4
8
5