A11128. Destiny

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 minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than  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$ and $q$ ( $1<=n,q<=3 \cdot 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$ and $k$ ( $1<=l<=r<=n,2<=k<=5$ ) — description of the queries.

Output answer for each query in new line.