Migrated from Lutece 3120 跳跃的世界线

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：主席树

“就算知道方法，也绝对不能去改变过去，绝不能将存在的可能性转变为既定的现实，未来是没有人能预测的，是无法重来的，正因如此人们才能接受各种痛苦，不幸与飞来横祸，迈步前进。”

给定长为 $n$ 的序列 $\{a\}$，总共 $Q$ 次询问。询问形如 l r k ，表示询问区间 $[l,r]$ 中，出现次数严格大于 $\frac{r-l+1}{k}$ 的最小值是多少。如果不存在这样的值，输出 -1 。

Input

第一行，两个正整数 $n,Q$。 第二行，共 $n$ 个正整数，第 $i$ 个数表示 $a_i$ 的值。 接下来 $Q$ 行，每行三个正整数 l r k，表示一组询问。

Output

每行一个整数，表示询问的答案。

Samples

8 3
1 3 2 2 1 3 1 1
2 6 3
1 4 2
3 8 3

2
-1
1

Constraints

$1\leq n,q\leq 10^5$，$2\leq k \leq 5$，$1\leq a_i\leq 10^9$

Resources

2024 UESTC ICPC Training for Data Structures