There are N noxious traps. The ith noxious trap contains Ni mushrooms.

Teemo usually asks Amumu, "Do you know the Kth largest mushroom number during N[i..j]?".

There are muti-case.
For each test case, the first line contains two integer N (0 < N < 100,000) and M (0 < M < 5,000) , N means the number of the nouxious trap, M means the times Teemo asked Amumu.
The next line contains N integers, means ith noxious trap contains Ni mushrooms.
The next M lines, for each line, there are three integers I, J, K (1 ≤ I ≤ J ≤ N, 1 ≤ K ≤ J - I + 1). I means the start trap number, J means the end trap number.

For each question that Teemo asked, you have to print the answer for a line.