K-th Number 2

Time Limit: 3 s Memory Limit: 64 MB

Submission：35 AC：6 Score：99.85

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<=500000,1<=M<=1000000

Author