有一次,Leha 在左边的口袋里发现了一个由 n 个整数组成的数组,在右边的口袋里发现了 q 个 l r k 形式的查询。如果有疑问,则必须予以答复。查询的答案是最小的 x,使得 x 在区间 l r 中出现严格超过 $$\frac{r-l+1}{k}$$ 次,如果没有这样的数字,则为 - 1。帮助莱哈完成如此艰巨的任务。
输入
输入数据的第一行包含两个整数 n 和 q (1 ≤ n, q ≤ 3·105) — 分别是数组中的元素数量和查询数量。
下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n) — Leha 的数组。
接下来的 q 行包含三个整数 l、r 和 k (1 ≤ l ≤ r ≤ n, 2 ≤ k ≤ 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