Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l\ r\ k$. If there are queries, then they must be answered. Answer for the query is minimalxsuch that $x$ occurs in the intervallrstrictly more than $\frac{r-l+1}{k}$ times or $-1$ if there is no such number.
Help Leha with such a difficult task.

First line of input data contains two integers $n,q\ (1≤n,q≤3·10^5)$ − number of elements in the array and number of queries respectively.

Next line contains $n$ integers $a_1,a_2,...,a_n\ (1≤a_i≤n)$ − Leha's array.

Each of next $q$ lines contains three integers $l,r,k\ (1≤l≤r≤n,\ 2≤k≤5)$ − description of the queries.

Output answer for each query in new line.