时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定一个长度为 \(n\) 的整数数组 \(A[1]、A[2]、…、A[n](-10^9≤A[i]≤10^9)\)，和 \(m\) 个询问。

　　每个询问的格式为: \(x\ y\ v（1 ≤ x < y ≤ n,-10^9 ≤ v ≤ 10^9）\) 表示询问 \(A[x]..A[y]\) 中小于 \(v\) 的最大值。

【输入格式】

　　第一行包含两个整数 \(n\) 和 \(m\)，表示数组有 \(n\) 个元素，\(m\) 表示有 \(m\) 个查询；
　　接下来的一行包含 \(n\) 个整数，第 \(i\) 个整数表示 \(A[i]\)；
　　再接下来的 \(m\) 行，每行一个操作。

【输出格式】

　　按输入顺序查询的结果，如果没有答案，则输出 None。

【输入输出样例】

　Input

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

　Output

6
3
None

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤n,m≤200000\)。

【来源】

　　Mr.he