Cho một dãy số \(N\) phần tử \(a_1, a_2,...,a_N\ (1 \le N \le 10^5,|a_i|\le 10^9)\). Hãy viết chương trình trả lời các câu hỏi có dạng \(Q(i,j,k)\) với ý nghĩa: tìm số thứ \(k\) trong dãy số \(a_i, a_2,...,a_j\) sau khi ta sắp xếp dãy số này theo thứ tự tăng dần \((1 \le i,j \le N, 1 \le k \le j-i+1)\).

Input

Đọc từ file văn bản KTHNUM.INP có cấu trúc:

• Dòng đầu ghi 2 số \(N\) và \(M\) (\(M\) là số câu hỏi, \(M \le 5000\)).
• Dòng 2 ghi \(N\) số \(a_1, a_2,...,a_N\).
• \(M\) dòng tiếp theo, mỗi dòng ghi 3 số \(i,j,k\) tương ứng với một câu hỏi.

Output

• Ghi ra file văn bản KTHNUM.OUT gồm \(M\) dòng, mỗi dòng ghi một số là câu trả lời tương ứng với một câu hỏi.

Example

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

5
6
3