2306: sequence

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:7 Solved:3

Description

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

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

Input

第一行两个正整数nm。

第二行n 个数,表示序列A1A2......An。

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

Output

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

Sample Input Copy

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

Sample Output Copy

1
3
4

HINT

nth_element

Source/Category