题目描述

给定一个长度为 $N$ 的正整数数列，有 $Q$ 个询问，每次提问一个区间 $l,r$ 和一个正整数$x$，输出区间里，最靠右的第一个比它小的数，如果不存在则输出 $−1$。

输入格式

第一行包含整数 $N,Q$，表示数列长度和提问个数。

第二行包含 $N$ 个整数，表示整数数列。

接下来 $Q$ 行，每行三个整数 $l,r,x$

输出格式

共 $Q$ 行，表示每个提问的答案。

样例

输入样例

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

输出样例

2
2
-1

提示

对于 $\red{100\% }$的数据 $\red{N, Q\leq 10^5}$，数列中的所有数都不超过 $\red{10^9}$。