A10226. 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_{pi}≠x_{i}$ .

The first line contains two integers $n,m$ ( $1<=n,m<=2·10^{5}$ ) — the number of elements in $a$ and the number of queries.

The second line contains $n$ integers $a_{i}$ ( $1<=a_{i}<=10^{6}$ ) — 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}<=10^{6}$ ) — the parameters of the $i$ -th query.

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.