可怜的狗狗

题目背景

小卡由于公务需要出差,将新家中的狗狗们托付给朋友嘉嘉,但是嘉嘉是一个很懒的人,他才没那么多时间帮小卡喂狗狗。

题目描述

小卡家有N只狗,由于品种、年龄不同,每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比(漂亮值越低越漂亮),吃饭时,狗狗们会按顺序站成一排等着主人给食物。 可是嘉嘉真的很懒,他才不肯喂这么多狗呢,这多浪费时间啊,于是他每次就只给第i只到第j只狗中第k漂亮的狗狗喂食(好狠心的人啊)。而且为了保证某一只狗狗不会被喂太多次,他喂的每个区间(i,j)不互相包含。

输入输出格式

输入格式


第一行输入两个数n,m,你可以假设n<300001 并且 m<50001;m表示他喂了m次。 第二行n个整数,表示第i只狗的漂亮值为ai。 接下来m行,每行3个整数i,j,k表示这次喂食喂第i到第j只狗中第k漂亮的狗的漂亮值。

输出格式


M行,每行一个整数,表示每一次喂的那只狗漂亮值为多少。

输入输出样例

输入样例 #1

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

输出样例 #1

3
2