#2542. 区间第 k 小
区间第 k 小
Description
午餐时,狗会从到 站成一排,最左边的是。每只狗都有一个美丽值,美丽值越低越漂亮。每次喂食时,佳佳都会选择[ , ]区间第 漂亮的狗喂食。喂食区间可以相互交叉,不存在完全包含的情况。帮助佳佳计算每一次喂食后,哪只狗吃了食物。
Input
第行输入含 和 ,分别表示狗的数量和喂食的数量;第行输入 个整数,从左到右描述每只狗的美丽值;接下来的 行,每行都包含个整数、、 ,表示喂养区间[ , ]第 漂亮的狗,, 。
Output
输出包含 行,第 行输出第 次喂食的狗的美丽值。
Samples
7 2
1 5 2 6 3 7 4
1 5 3
2 7 1
3
2
来源
POJ2761