题目描述

一次，$\text{Leha}$ 在左口袋里找到了一个由 $n$ 个整数组成的数组，在右口袋里找到了 $q$ 个形如 $l~r~k$ 的查询。如果有查询，那么它们必须被回答。查询的答案是最小的 $x$，使得 $x$ 出现在区间 $[l,r]$ 中的次数严格大于$\frac {r-l+1}{k}$ 次，如果没有这样的数字，则输出 $- 1$。帮助 $\text{Leha}$ 完成这个困难的任务。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $q$，表示数组中元素的数量和查询的数量。

接下来一行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le n$)，表示 $\text{Leha}$ 的数组。

接下来的每一行包含三个整数 $l$,$r$ 和 $k$ ($1 \le l \le r \le n$,  $2 \le k \le 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

样例分析

对于样例 $1$：

第一次询问，最小的是 $1$，使得 $1$ 出现在区间 $[1,3]$ 中的次数严格大于$\frac {3-1+1}{2}$ 次；

第二次询问，不存在一个数，使得这个数出现在区间 $[1,4]$ 中的次数严格大于$\frac {4-1+1}{2}$ 次，输出 $-1$。

数据范围与提示

对于 $100\%$ 的数据： $1 \le n,q \le 3\times 10^5$ 。