Cho một dãy gồm ~𝑛~ số nguyên ~a_1,a_2,…,a_n~ và ~m~ câu truy vấn. Mỗi câu truy vấn gồm 3 số ~u,v,k~ với ý nghĩa: nếu sắp xếp các số trong đoạn từ ~a_u,a_{u+1},…,a_v~ thì số thứ ~k~ trong đoạn đó là số nào?

Yêu cầu: Cho ~m~ câu truy vấn, hãy đưa ra câu trả lời cho từng câu truy vấn đã cho.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ~n,m~ ~(n≤10^5,m≤10^3)~;
• Dòng thứ hai chứa ~𝑛~ số nguyên ~a_1,a_2,…,a_n~ ~(|a_i |≤10^5)~, các số cách nhau bởi dấu cách.
• ~m~ dòng tiếp theo, mỗi dòng ghi 3 số ~u, v, k~ cho biết một truy vấn.

Kết quả:

• Gồm ~m~ dòng, mỗi dòng là một câu trả lời tương ứng với từng câu truy vấn đã cho ở trên.

Ví dụ:

Input:

10 10
1 7 14 0 9 4 18 18 2 4
6 6 1
2 8 2
3 6 4
2 7 1
3 4 1
2 3 1
6 9 4
2 7 1
3 10 4
6 10 5 

Output:

4
4
14
0
0
7
18
0
4
18