K-th Number (Easy)#1150
You are working for Macrohard company in the data structures department. After your unsuccessful previous attempt at solving the key insertion problem, you have been asked to design a new data structure that can quickly find the k-th order statistic in a given array segment.
You are given an array a[1 \ldots n] of distinct integer numbers. You must answer queries of the form Q(i, j, k): "Find the -th number in the subarray a[i \ldots j] if all its elements are sorted."
For example, consider a = (1, 5, 2, 6, 3, 7, 4). For the query Q(2, 5, 3), the subarray a[2 \ldots 5] = (5, 2, 6, 3). Sorting this segment gives (2, 3, 5, 6), so the third number is ; thus, the answer is .
The first line contains the size of the array and the number of queries (1 \le n, m \le 100).
The second line contains distinct integers whose absolute values do not exceed 10^9 -- the array .
Each of the next lines contains three integers: , , and (1 \le i \le j \le n, 1 \le k \le j-i+1) representing a query Q(i, j, k).
For each query, output the -th number in the sorted segment a[i \ldots j].
Example 1