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 \le n,q \le 3 \cdot 105) - number of elements in the array and number of queries respectively.

Next line contains n integers a1,a2,...,an (1 \le ai \le n) - Leha's array.

Each of next q lines contains three integers l, r and k (1 \le l \le r \le n,2 \le k \le 5) - description of the queries.

Output answer for each query in new line.