길이가 \(N\)인 수열 \(A_1, A_2, \dots, A_N\)이 주어진다. 이때 다음 쿼리를 수행하는 프로그램을 작성하시오.

• i j k: \(A_i, A_{i+1}, \dots, A_j\) 구간의 원소들을 오름차순으로 정렬했을 때, \(k\)번째로 오는 원소를 출력한다.

입력

첫 번째 줄에 수열의 크기 \(N\)과 쿼리의 개수 \(Q\)가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열의 원소 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.

세 번째 줄부터 \(Q\)개의 줄에 걸쳐 각 쿼리를 나타내는 세 정수 \(i, j, k\)가 공백으로 구분되어 주어진다.

\((2 \le N \le 100,000)\)

\((1 \le Q \le 100,000)\)

\((-10^9 \le A_i \le 10^9)\)

\((1 \le i \le j \le N)\)

\((1 \le k \le j - i + 1)\)

출력

각 쿼리의 정답을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

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

예제 출력 1

5
6
3