Stock Heat Query

There are \(N\) people queued for trading, and each person holds exactly one type of stock. Note that different people may hold the same stock. The heat of a stock is defined as the number of people holding that stock.

Will will ask a series of queries. In each query, given a continuous subarray of people from index \(L\) to \(R\) (1-indexed), you are to determine the heat of the stock which is the \(k\)-th smallest when sorting all the stocks (that appear in that subarray) by their heat in ascending order.

It is guaranteed that in every query, \(k\) does not exceed the number of distinct stocks in the queried interval.

Note: If there are multiple stocks with the same heat, they are considered as separate candidates when ranking.

inputFormat

The first line contains two integers \(N\) and \(Q\) --- the number of people and the number of queries, respectively.

The second line contains \(N\) integers, where the \(i\)-th integer represents the stock held by the \(i\)-th person.

Each of the next \(Q\) lines contains three integers \(L\), \(R\), and \(k\), describing a query.

outputFormat

For each query, output the heat (i.e. frequency) of the stock that is the \(k\)-th smallest in the queried subarray.

sample

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

2
1
1