题目背景

will 在曼哈顿开了一家交易所，每天，前来买卖股票的人络绎不绝。

现在，will 想要了解持股的情况。由于来交♂易的人实在是太多了，需要你写一个程序来帮他完成这个任务。

题目描述

• 前来交易的 $N$ 个人排成了一行，为了简便起见，每个人都只持有一种股票。
• 不同的的人可能会持有相同的股票。
• 定义一种股票的热度为持有该股票的人数。
• 每次，will 会给出这样的询问：在一段连续区间的人之中，热度第 $k$ 小的股票的热度是多少？

输入格式

• 第一行两个正整数 $N,M$，分别表示人数和询问的次数。
• 接下来一行 $N$ 个正整数，表示每个人所持的股票 $a_i$。
• 接下来 $M$ 行，每行三个正整数 $l,r,k$，表示询问区间 $[l, r]$ 中的第 $k$ 小的热度，保证 $l\leq r$。

输出格式

• 对于每个询问，输出一行一个数，表示区间 $[l, r]$ 中的第 $k$ 小的热度值。
• 如果 $k$ 大于区间里股票的种类数，输出 $-1$。

4 4  
2 3 3 3  
1 4 1  
1 4 2  
1 3 2
1 3 3

1  
3  
2  
-1

提示

对于 $20\%$ 的数据，$N,M\leq 1000$。

对于另外 $10\%$ 的数据，所有的 $l=1, r=N$。

对于 $100\%$ 的数据，$1\leq N, M\leq 10^5$，$1\leq a_i\leq 10^9$。