Destiny

题意翻译

给定$n$个元素，$m$次询问。 每次给出三个参数$l,r,k$，询问区间$[l,r]$内是否存在出现次数严格大于$\frac{r-l+1}{k}$的数。如果存在就输出最小的那个$ans$，否则输出$-1$.

题目描述

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·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.

输入输出样例

输入样例 #1

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

输出样例 #1

1
-1

输入样例 #2

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

输出样例 #2

2
1
2