CF840D.Destiny

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.

曾经，Leha 在左口袋中发现了一个由 $n$ 个整数组成的数组，在右口袋中发现了 $q$ 个形如 $l\ r\ k$ 的查询。若存在查询，则必须回答它们。每个查询的答案为最小的 $x$，使得 $x$ 在区间 $[l,\ r]$ 中出现的次数严格大于 $\frac{r-l+1}{k}$，若不存在这样的数，则答案为 $-1$。请帮助 Leha 完成这项困难的任务。

First line of input data contains two integers n and q (1 ≤ n, q ≤ 3·105) — 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.

输入数据的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3\cdot10^5$）—— 分别表示数组的元素个数和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \le a_i \le n$）—— Leha 的数组。

接下来的 $q$ 行，每行包含三个整数 $l$、$r$ 和 $k$（$1 \le l \le r \le n$, $2 \le k \le 5$）—— 查询的描述。

Output answer for each query in new line.

每个查询的答案输出在新的一行。