对于任意非负整数构成的多重集 $S$（$S$ 中可能包含重复元素），定义 $\text{mex}(S)$ 为 $S$ 中未出现的最小非负整数。

给定一个包含 $n$ 个非负整数的序列 $A_1, A_2, \dots, A_n$ 以及 $q$ 次询问。

对于任意区间 $[l, r]$ ($1 \le l \le r \le n$)，定义其权值为 $\text{mex}([l, r]) = \text{mex}(\{A_l, A_{l+1}, \dots, A_r\})$。

对于每次询问，给定一个区间 $[L, R]$ 和一个正整数 $k$，求区间 $[L, R]$ 内所有子区间的权值中，第 $k$ 小的权值。

输入格式

第一行包含两个整数 $n, q$ ($n, q \le 10^5$)，分别表示序列的长度和询问的次数。

第二行包含 $n$ 个非负整数 $A_1, A_2, \dots, A_n$ ($0 \le A_i \le n$)，以空格分隔。

接下来的 $q$ 行，每行包含三个整数 $L, R, k$ ($1 \le L \le R \le n, 1 \le k \le \frac{(R-L+1)(R-L+2)}{2}$)，表示一次询问。

输出格式

输出 $q$ 行。第 $i$ 行应包含第 $i$ 次询问的答案。

样例

输入 1

5 5
1 0 3 0 2
1 5 3
3 4 2
1 3 4
1 3 3
2 2 1

输出 1

0
1
1
1
1