F-整数游戏

题面描述

通过写完国庆作业，小青发现有人在她的口袋里塞了一些神秘整数，需要完成一些整数游戏

小青在左边口袋里发现了一个包含 $n$ 个整数的数组，在右边口袋里发现了 $q$ 个询问，每个询问的形式为 $l$ $r$ $k$。如果有询问，那么必须回答。对于每个询问，回答的是满足在区间 $l$ 到 $r$ 中出现次数严格大于 $\left\lfloor \frac{r-l+1}{k} \right\rfloor$ 次的最小 $x$，如果不存在这样的数字，输出 $-1$。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$，分别表示数组的大小和询问的个数。（$1 \leq n, q \leq 3 \cdot 10^5$）

下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示 小青的数组。（$1 \leq a_i \leq n$）

接下来的 $q$ 行中，每行包含三个整数 $l$、$r$ 和 $k$，表示每个询问。（$1 \leq l \leq r \leq n, 2 \leq k \leq 5$）

输出格式

对于每个询问，输出一行答案。

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