K번째 수

어떤 배열의 특정 구간을 정렬한 뒤, 그 안에서 지정된 순위의 값을 구하는 함수를 만들려고 합니다.

크기가 $n$인 배열 $a[1 \dots n]$에는 서로 다른 정수 $n$개가 저장되어 있습니다. 이 배열에 대해 다음과 같은 함수 $Q(i, j, k)$를 정의합니다.

$Q(i, j, k)$: 부분 배열 $a[i \dots j]$를 오름차순으로 정렬했을 때 $k$번째로 작은 값을 반환하는 함수

예를 들어 $a = (1, 5, 2, 6, 3, 7, 4)$일 때 $Q(2, 5, 3)$을 계산해 봅시다. $a[2 \dots 5]$는 $(5, 2, 6, 3)$이고, 이를 정렬하면 $(2, 3, 5, 6)$이 됩니다. 정렬된 배열에서 3번째 값은 5이므로 $Q(2, 5, 3) = 5$입니다.

배열 $a$와 여러 개의 질의 $Q(i, j, k)$가 주어질 때, 각 질의의 반환값을 출력하는 프로그램을 작성하세요.

첫째 줄에 배열의 크기 $n$과 질의의 개수 $m$이 공백으로 구분되어 주어집니다. ($1 \le n \le 100{,}000$, $1 \le m \le 5{,}000$)

둘째 줄에 배열의 원소 $n$개가 순서대로 주어집니다. 각 원소는 절댓값이 $10^9$ 이하인 정수이며, 모든 원소는 서로 다릅니다.

이어지는 $m$개의 줄에 각 질의의 인자 $i$, $j$, $k$가 주어집니다. ($1 \le i \le j \le n$, $1 \le k \le j - i + 1$)

각 질의마다 $Q(i, j, k)$의 반환값을 한 줄에 하나씩 출력합니다.