CF622C.Not Equal on a Segment

You are given array a with n integers and m queries. The i-th query is given with three integers l__i, r__i, x__i.

For the i-th query find any position p__i (l__i ≤ p__i ≤ r__i) so that a__p__i ≠ x__i.

给你一个包含 $n$ 个整数的数组 $a$，以及 $m$ 个查询。第 $i$ 个查询由三个整数 $l_i,\, r_i,\, x_i$ 给出。

对于第 $i$ 个查询，请在区间 $[l_i,\, r_i]$ 内找出任意一个位置 $p_i$（即满足 $l_i \leq p_i \leq r_i$），使得 $a_{p_i} \neq x_i$。

The first line contains two integers n, m (1 ≤ n, m ≤ 2·105) — the number of elements in a and the number of queries.

The second line contains n integers a__i (1 ≤ a__i ≤ 106) — the elements of the array a.

Each of the next m lines contains three integers l__i, r__i, x__i (1 ≤ l__i ≤ r__i ≤ n, 1 ≤ x__i ≤ 106) — the parameters of the i-th query.

第一行包含两个整数 $n$、$m$（$1 \leq n, m \leq 2 \cdot 10^5$）—— 分别表示数组 $a$ 的元素个数和查询次数。

第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^6$）—— 表示数组 $a$ 的元素。

接下来的 $m$ 行，每行包含三个整数 $l_i$、$r_i$、$x_i$（$1 \leq l_i \leq r_i \leq n$，$1 \leq x_i \leq 10^6$）—— 表示第 $i$ 个查询的参数。

Print m lines. On the i-th line print integer p__i — the position of any number not equal to x__i in segment [l__i, r__i] or the value  - 1 if there is no such number.

输出 m 行。在第 i 行输出整数 p__i —— 即区间 [l__i, r__i] 中任意一个不等于 x__i 的数的位置；若不存在这样的数，则输出  - 1。