说明

给出一个长度为$n$的序列$A_{1},A_{2},A_{3}\cdots A_{n}$，其中每项都是小于$10^{5}$的自然数。

现在有$m$个询问，每个询问都是$A_{i}\cdots A_{j}$中第$k$小的数等于多少。

输入格式

第一行两个正整数$n，m$

第二行$n$个数，表示序列$A_{1},A_{2},A_{3}\cdots A_{n}$

紧着的$m$行，每行三个正整数$i,j,k$，表示询问$A_{i}\cdots A_{j}$中第$k$小的数等于多少。

输出格式

共输出$m$行，第$i$行输出第$i$个询问的答案。

样例

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

1
3
4

数据范围

• $n\leqslant200$
• $k\leqslant j-i+1$
• $0 \leq A_i \leq 10^5$