K-th Number

Time Limit: 3 s Memory Limit: 16 MB

Submission：116 AC：8 Score：99.64

Description

在一个长度为N的序列中给出M个询问，求区间第K小的数。

Input

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

Output

1
3

Hint

1 <=N,M<=100000

Author