可怜的狗狗

题目描述

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

输入输出格式

输入格式


第一行输入两个数 $n,m$, $m$ 表示嘉嘉喂食的次数 第二行 $n$ 个整数,表示第 $i$ 只狗的漂亮值为 $a_i$。 接下来 $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

说明

$1\le n \le 3\times 10^5 ,1\le m \le5\times10^4,0\le a_i<2^{31}$,且 $a_i$ 互不相同。