Ocean Waves Query

You are given an array representing the sea wave heights at consecutive time moments. Your task is to answer several queries. For each query, you are given three integers x, y, and k. You need to consider the subarray from time x to y (inclusive). Each moment is associated with a pair (wave height, time index). Sort this subarray by wave height in ascending order. In case of a tie in wave height, the smaller time index comes first. Then, output the time moment (i.e. the original index) corresponding to the kth element in this sorted order.

Input Format: The first line contains two integers n and m where n is the number of time moments and m is the number of queries. The second line contains n integers representing the wave heights. The following m lines each contain three integers x, y, and k, representing a query.

Output Format: For each query, output one line with the answer — the time moment (original index) that is the kth smallest when the subarray is sorted by (wave height, time index).

Performance Requirement: Your program should run within 1 second.

Note (in LaTeX):

The {% raw %}$k$th{% endraw %} smallest element in the subarray \([x, y]\) is defined as follows: if we denote the subarray by \(a_x, a_{x+1}, \dots, a_y\) and sort it into \(b_1 \leq b_2 \leq \dots \leq b_{y-x+1}\) (with ties broken by the original index), then the answer is the original index corresponding to \(b_k\).

inputFormat

The first line contains two integers n and m. The second line contains n integers representing the sea wave heights at time moments 1 through n. Each of the following m lines contains three integers x, y, and k, representing a query that asks for the kth smallest element (sorted by height, and then by time index if there is a tie) among the time moments from x to y (inclusive).

outputFormat

For each query, output a single integer representing the time moment (i.e., the original index) where the kth smallest sea wave height occurs in the interval. Each answer should be printed on its own line.

sample

5 3
3 1 4 1 5
1 5 2
2 4 1
3 3 1

4
2
3