Description

午餐时，狗会从$1$到$n$ 站成一排，最左边的是$1$。每只狗都有一个美丽值，美丽值越低越漂亮。每次喂食时，佳佳都会选择[$i$ , $j$ ]区间第$k$ 漂亮的狗喂食。喂食区间可以相互交叉，不存在完全包含的情况。帮助佳佳计算每一次喂食后，哪只狗吃了食物。

Input

第$1$行输入含$n$ 和$m$ ，分别表示狗的数量和喂食的数量；第$2$行输入$n$ 个整数，从左到右描述每只狗的美丽值；接下来的$m$ 行，每行都包含$3$个整数$i$、$j$、$k$ ，表示喂养区间[$i$ , $j$ ]第$k$ 漂亮的狗，$n$$<$$1$$0$$0$$0$$0$$1$，$m$ $<$$5$$0$$0$$0$$1$。

Output

输出包含$m$ 行，第$i$ 行输出第$i$ 次喂食的狗的美丽值。

Samples

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

3
2

来源

POJ2761