Destiny

题意翻译

给定 $n$ 个元素,$q$ 次询问。 每次给出三个参数 $l, r, k$,询问区间 $[l, r]$ 内是否存在出现次数严格大于 $\frac{r - l + 1} {k}$ 的数。如果存在就输出最小的那个数,否则输出 $-1$。 $1\leq n, q\leq 3\times 10 ^ 5$,$1\leq a_i\leq n$,$2\leq k\leq 5$。

题目描述

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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF840D/c2e8ec3f500434412245cc8e8d90787dc635e07f.png) 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.

输入输出样例

输入样例 #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