题目描述

给定长度为$\red {N}$的整数序列$\red {A}$，下标为 $\red {1∼N}$。

现在要执行$\red {M}$次操作，其中第$\red i$次操作为给出三个整数$\red {l _i~ ,r _i~ ,k _i~}$ ，求$\red {A[l_i~ ],A[l _i~ +1],…,A[r_i~]}$中第$\red {k_i~}$小的数是多少。

输入格式

第一行包含两个整数$\red {N}$和$\red {M}$。

第二行包含$\red {N}$个整数，表示整数序列$\red {A}$。

$\red {M}$行，每行包含三个整数$\red {l _i~ ,r _i~ ,k _i~ }$，用以描述第$\red {i}$次操作。

输出格式

对于每次操作输出一个结果，表示在该次操作中，第$\red {k}$小的数的数值。

每个结果占一行。

样例

输入样例

7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

输出样例

5
6
3

提示

$\red {N≤10 ^5,M≤10 ^4 ,|A[i]|≤10^9}$