JUNGOL

배열 a[1...n]에는 서로 다른 수가 n개 저장되어 있다. 우리의 목적은 Q(i,j,k)라는 함수를 구현하는 것이다.

예를 들어, a = (1,5,2,6,3,7,4)인 경우 Q(2,5,3)의 답을 구하는 과정을 살펴보자.

a[2...5]는 (5,2,6,3)이고, 이 배열을 정렬하면 (2,3,5,6)이 된다. 정렬한 배열에서 3번째 수는 5이다. 따라서 Q(2,5,3)의 리턴 값은 5이다.

배열 a가 주어지고, Q함수를 호출한 횟수가 주어졌을 때, 각 함수의 리턴 값을 출력하는 프로그램을 작성하시오.

Entrada

첫째 줄에 배열의 크기 n과 함수 Q를 호출한 횟수 m이 주어진다. (1 ≤ n ≤ 500,000, 1 ≤ m ≤ 5,000)

둘째 줄에는 배열에 포함된 정수가 순서대로 주어진다. 각 정수는 절댓값이 10^9를 넘지 않는 정수이다.

다음 m개 줄에는 Q(i,j,k)를 호출할 때 사용한 인자 i,j,k가 주어진다. (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j-i+1)

Salida

Q함수를 호출할 때마다 그 함수의 리턴값을 한 줄에 하나씩 출력한다.

Subtarea

#	Puntaje	Condición
#1	80	1 ≤ n ≤ 100,000
#2	20

Ejemplo

Etiqueta

Fuente

NEERC Northern Subregional 2004 K번

K번째 수 1s 1024MB