As it is known, Tobby loves arrays and queries (he also hates long statements :D). One day Tobby came up with the following: there is an array of integers and multiple queries. For each query, Tobby wants to know the value of the k-th position in the subarray [l, r] (r ≥ l) (1 ≤ k ≤ r − l + 1), if the subarray [l, r] was sorted in non-decreasing order. Input The input has several test cases. The first line contains n (1 ≤ n ≤ 106) and q (1 ≤ q ≤ 106), the length of the array and the number of queries respectively. The next line contains n integers ai (1 ≤ ai ≤ 109). Then q lines follow, each line containing a query with three integers l, r and k (1 ≤ l, r ≤ n). Output For each query print the answer in a single line (Look at the samples). Explanation: For the first sample. indexes: 1 2 3 4 array = {1, 3, 4, 3} For first query [1, 2] we have the subarray {1, 3}, after sorting we have {1, 3}, so the value in the 2-th position is 3. For second query [2, 4] we have the subarray {3, 4, 3}, after sorting we have {3, 3, 4}, so the value in the 1-th position is 3. For third query [1, 4] we have the subarray {1, 3, 4, 3}, after sorting we have {1, 3, 3, 4}, so the value in the 4-th position is 4. Sample Input 43 1343 122 241 144 83 47853612 451 183 353 10 10 8 6 2 1 7 3 10 9 5 4 183 771 781 991 2 10 9 272 571
2/2 10 10 1 9 10 2 7 10 4 Sample Output 3 3 4 3 3 8 3 10 9 5 10 2 3 4 5 10