시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB99912925165331.954%

문제

현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다.

현정이가 만든 자료구조는 배열을 응용하는 것이다. 배열 a[1...n]에는 서로 다른 수가 n개 저장되어 있다. 현정이는 여기에 Q(i,j,k)라는 함수를 구현해 모두를 놀라게 할 것이다.

Q(i,j,k): 배열 a[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함수를 호출한 횟수가 주어졌을 때, 각 함수의 리턴값을 출력하는 프로그램을 작성하시오.

입력

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

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

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

출력

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

예제 입력 1

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

예제 출력 1

5
6
3
W3sicHJvYmxlbV9pZCI6Ijc0NjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJLXHViYzg4XHVjOWY4IFx1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNjA0XHVjODE1XHVjNzc0XHViMjk0IFx1Yzc5MFx1YjhjYyBcdWFkNmNcdWM4NzAgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHViOTdjIFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjJlNFx1Yjk3OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4IFx1YzhmY1x1YzgxY1x1Yjg1YyBcdWMyYTRcdWQwZGQsIFx1ZDA1MFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZTMwXHViY2Y4IFx1Yzc5MFx1YjhjYyBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhZDZjXHVkNjA0XHVkNTU4XHViMjk0IFx1YzhmY1x1YzgxY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVkNjA0XHVjODE1XHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM3OTBcdWI4Y2MgXHVhZDZjXHVjODcwXHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjODE1XHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlMCBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzBcdWIyOTQgXHViYzMwXHVjNWY0XHVjNzQ0IFx1Yzc1MVx1YzZhOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YmMzMFx1YzVmNCBhWzEuLi5uXVx1YzVkMFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzIxOFx1YWMwMCBuXHVhYzFjIFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1ZDYwNFx1YzgxNVx1Yzc3NFx1YjI5NCBcdWM1ZWNcdWFlMzBcdWM1ZDAgUShpLGosaylcdWI3N2NcdWIyOTQgXHVkNTY4XHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDYwNFx1ZDU3NCBcdWJhYThcdWI0NTBcdWI5N2MgXHViMTgwXHViNzdjXHVhYzhjIFx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPlxyXG48cD5RKGksaixrKTombmJzcDtcdWJjMzBcdWM1ZjQgYVtpLi4ual1cdWI5N2MgXHVjODE1XHViODJjXHVkNTg4XHVjNzQ0IFx1YjU0Yywga1x1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgXHViOWFjXHVkMTM0XHVkNTU4XHViMjk0IFx1ZDU2OFx1YzIxODxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBhID0gKDEsNSwyLDYsMyw3LDQpXHVjNzc4IFx1YWNiZFx1YzZiMCBRKDIsNSwzKVx1Yzc1OCBcdWIyZjVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWMwYjRcdWQzYjRcdWJjZjRcdWM3OTAuIGFbMi4uLjVdXHViMjk0ICg1LDIsNiwzKVx1Yzc3NFx1YWNlMCwgXHVjNzc0IFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWM4MTVcdWI4MmNcdWQ1NThcdWJhNzQgKDIsMyw1LDYpXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjODE1XHViODJjXHVkNTVjIFx1YmMzMFx1YzVmNFx1YzVkMFx1YzExYyAzXHViYzg4XHVjOWY4IFx1YzIxOFx1YjI5NCA1XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgUSgyLDUsMylcdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQwIDVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMFx1YzVmNCBhXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgUVx1ZDU2OFx1YzIxOFx1Yjk3YyBcdWQ2MzhcdWNkOWNcdWQ1NWMgXHVkNjlmXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMSBcdWQ1NjhcdWMyMThcdWM3NTggXHViOWFjXHVkMTM0XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWFjZmMgXHVkNTY4XHVjMjE4IFFcdWI5N2MgXHVkNjM4XHVjZDljXHVkNTVjIFx1ZDY5Zlx1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwLDAwMCwgMSAmbGU7IG0gJmxlOyA1LDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODE1XHVjMjE4XHViMjk0IFx1YzgwOFx1YjMxM1x1YWMxMlx1Yzc3NCAxMDxzdXA+OTxcL3N1cD5cdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBRKGksaixrKVx1Yjk3YyBcdWQ2MzhcdWNkOWNcdWQ1NjAgXHViNTRjIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWM3NzhcdWM3OTAgaSxqLGtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IGkgJmxlOyBqICZsZTsgbiwgMSAmbGU7IGsgJmxlOyBqLWkrMSk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5RXHVkNTY4XHVjMjE4XHViOTdjIFx1ZDYzOFx1Y2Q5Y1x1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVhZGY4IFx1ZDU2OFx1YzIxOFx1Yzc1OCBcdWI5YWNcdWQxMzRcdWFjMTJcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijc0NjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLLXRoIE51bWJlciIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSB3b3JraW5nIGZvciBNYWNyb2hhcmQgY29tcGFueSBpbiBkYXRhIHN0cnVjdHVyZXMgZGVwYXJ0bWVudC4gQWZ0ZXIgZmFpbGluZyB5b3VyIHByZXZpb3VzIHRhc2sgYWJvdXQga2V5IGluc2VydGlvbiB5b3Ugd2VyZSBhc2tlZCB0byB3cml0ZSBhIG5ldyBkYXRhIHN0cnVjdHVyZSB0aGF0IHdvdWxkIGJlIGFibGUgdG8gcmV0dXJuIHF1aWNrbHkgay10aCBvcmRlciBzdGF0aXN0aWNzIGluIHRoZSBhcnJheSBzZWdtZW50LjxcL3A+XHJcblxyXG48cD5UaGF0IGlzLCBnaXZlbiBhbiBhcnJheSBhWzEuLi5uXSBvZiBkaWZmZXJlbnQgaW50ZWdlciBudW1iZXJzLCB5b3VyIHByb2dyYW0gbXVzdCBhbnN3ZXIgYSBzZXJpZXMgb2YgcXVlc3Rpb25zIFEoaSwgaiwgaykgaW4gdGhlIGZvcm06ICZsZHF1bztXaGF0IHdvdWxkIGJlIHRoZSBrLXRoIG51bWJlciBpbiBhW2kuLi5qXSBzZWdtZW50LCBpZiB0aGlzIHNlZ21lbnQgd2FzIHNvcnRlZD8mcmRxdW87PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgYXJyYXkgYSA9ICgxLDUsMiw2LDMsNyw0KS4gTGV0IHRoZSBxdWVzdGlvbiBiZSBRKDIsNSwzKS4gVGhlIHNlZ21lbnQgYVsyLi4uNV0gaXMgKDUsMiw2LDMpLiBJZiB3ZSBzb3J0IHRoaXMgc2VnbWVudCwgd2UgZ2V0ICgyLDMsNSw2KSwgdGhlIHRoaXJkIG51bWJlciBpcyA1LCBhbmQgdGhlcmVmb3JlIHRoZSBhbnN3ZXIgdG8gdGhlIHF1ZXN0aW9uIGlzIDUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIG4gJm1kYXNoOyB0aGUgc2l6ZSBvZiB0aGUgYXJyYXksIGFuZCBtICZtZGFzaDsgdGhlIG51bWJlciBvZiBxdWVzdGlvbnMgdG8gYW5zd2VyICgxICZsZTsgbiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBtICZsZTsgNSAwMDApLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgbiBkaVx1ZmIwMGVyZW50IGludGVnZXIgbnVtYmVycyBub3QgZXhjZWVkaW5nIDEwPHN1cD45PFwvc3VwPiBieSB0aGVpciBhYnNvbHV0ZSB2YWx1ZXMgJm1kYXNoOyB0aGUgYXJyYXkgZm9yIHdoaWNoIHRoZSBhbnN3ZXJzIHNob3VsZCBiZSBnaXZlbi48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBtIGxpbmVzIGNvbnRhaW4gcXVlc3Rpb24gZGVzY3JpcHRpb25zLCBlYWNoIGRlc2NyaXB0aW9uIGNvbnNpc3RzIG9mIHRocmVlIG51bWJlcnM6IGksIGosIGFuZCBrICgxICZsZTsgaSAmbGU7IGogJmxlOyBuLCAxICZsZTsgayAmbGU7IGogJm1pbnVzO2krIDEpIGFuZCByZXByZXNlbnRzIHRoZSBxdWVzdGlvbiBRKGksIGosIGspLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHF1ZXN0aW9uIG91dHB1dCB0aGUgYW5zd2VyIHRvIGl0ICZtZGFzaDsgdGhlIGstdGggbnVtYmVyIGluIHNvcnRlZCBhW2kuLi5qXSBzZWdtZW50LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Northern Eurasia > North-Western Russia Regional Contest > NEERC Northern Subregional 2004 K번