题目描述

给定 $n$ 个元素，$q$ 次询问。

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

输入格式

第一行两个整数 $n,q$，$1\leq n, q\leq 3\times 10 ^ 5$。

第二行 $n$ 个整数 $a_i$，$1\leq a_i\leq n$。

接下来 $q$ 行，每行三个整数 $l,r,k$，$2\leq k\leq 5$。

输出格式

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

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

1
-1

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

2
1
2