题目描述

$Wind$非常喜欢漂亮的狗狗，她养了$n$只宠物狗。因此$Jiajia$每天都要替$Wind$喂狗。$Jiajia$爱$Wind$，但不喜欢这些狗，所以他用一种特殊的方式喂狗。午餐时间，这些狗会排成一列，编号从$1$到$n$（最左边的是$1$，其次是$2$，依此类推）。每次喂食时，$Jiajia$选择一个区间$[i,j]$，并喂食其中第$k$漂亮的狗。当然，$Jiajia$有自己判断每只狗漂亮值的方法。需要注意的是，$Jiajia$不希望过度喂食某个位置，因为这可能导致一些狗死亡。如果发生这种情况，$Wind$会生气，后果很严重。因此，任何喂食区间$[i,j]$都不能完全包含另一个喂食区间，尽管区间之间可以相互交叉。

你的任务是帮助$Jiajia$计算每次喂食后哪只狗吃了食物。

输入

第一行包含$n$和$m$，分别表示狗的数量和喂食次数。
第二行包含$n$个整数，按从左到右的顺序描述每只狗的漂亮值。注意，漂亮值较低的狗更漂亮。
接下来的$m$行，每行包含三个整数$i,j,k$，表示$Jiajia$在这次喂食中喂食区间$[i,j]$内第$k$漂亮的狗。
可以假设$n<100001$，$m<50001$。

输出

输出文件包含$m$行。第$i$行应包含第$i$次喂食中被喂食的狗的漂亮值。

样例输入

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

样例输出

3  
2  

来源

POJ Monthly--2006.02.26, zgl & twb