Tìm số bé thứ k trong đoạn i..j. Ví dụ :a = (1, 5, 2, 6, 3, 7, 4) và một câu hỏi là Q(2, 5, 3). Nghĩa là tìm số bé thứ 3 trong đoạn a[2..5]. Đáp số là 5.

Input

Dòng đầu tiên ghi n - số phần tử của mảng - và m, số truy vấn (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000). Dòng thứ hai gồm n số nguyên, có trị tuyệt đối <= 10^9. Tất cả các số đều khác nhau. Tiếp theo là m dòng,mỗi dòng có 3 số i, j, và k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j - i + 1).

SAMPLE INPUT
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Output

 
Mỗi dòng ghi kết quả của truy vấn tương ứng.

SAMPLE OUTPUT
5
6
3