← 返回题目列表

Codeforces · 840/D

D. 命运

中文机器翻译题面 查看原题

有一次,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