【试题描述】

给出一个长度为N 的序列A1,A2,......,An，其中每项都是小于100000 的自然数。

现在有m 个询问，每个询问都是Ai......Aj 中第k 小的数等于多少。

【输入要求】

第一行两个正整数n,m。

第二行n 个数，表示序列A1,A2,......,An。

紧接着的m 行，每行三个正整数i,j,k(k≤j-i+1)，表示询问Ai......Aj中第k 小的数等于多少。

【输出要求】

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

【输入样例】

4 3

4 1 2 3

1 3 1

2 4 3

1 4 4

【输出样例】

1

3

4

【解题提示】

nth_element