区间内第k项

难度：T2

【知识点：二分查找】【知识点：边界】

前置知识：数组、函数、循环、闭区间二分。

题目描述

给定按非降序排列的 $n$ 条非负数值记录。每次给出 $L,R,k$，只保留数值在闭区间 $[L,R]$ 内的记录，按原来的非降序顺序，输出第 $k$ 项的值。重复记录分别占一项；不足 $k$ 项时输出 $-1$。

规则说明

非降序表示从左到右，后一个数不小于前一个数，允许相等。例如 $1,2,2,5$ 是非降序，$1,3,2$ 不是。

输入格式

首行 $n,m$；第二行 $n$ 个非降序整数；随后输入 $m$ 次查询。每次三个整数 $L,R,k$。

输出格式

每个查询结果单独输出一行。

样例输入

5 3
4 7 7 10 15
7 12 2
7 12 4
0 20 5

样例输出

7
-1
15

数据范围

$1\le n,m\le20000$，数组元素及查询数值、范围端点均为 $0$ 到 $10^9$。每次保证 $L\le R$。$1\le k\le20001$。