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}.


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
6 4
1 2 1 1 3 5
1 4 1
2 6 2
3 4 1
3 4 2

Output
2
6
-1
4

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation


Solutions:
import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
cat = ''.join
catn = '\n'.join
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
(n, m) = ris()
a = ris()
p = [n] * n
stk = []
for i in range(n):
	while stk and a[stk[-1]] != a[i]:
		p[stk.pop()] = i
	stk.append(i)
for _ in range(m):
	(l, r, x) = ris()
	(l, r) = (l - 1, r - 1)
	if a[l] != x:
		print(l + 1)
	elif p[l] <= r:
		print(p[l] + 1)
	else:
		print(-1)


import sys
(n, m) = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
assert len(a) == n
prev = [-1] * n
l = r = 0
while l < n:
	while r < n and a[l] == a[r]:
		r += 1
	for i in range(l, r):
		prev[i] = l - 1
	l = r
for i in range(m):
	(l, r, x) = map(int, sys.stdin.readline().split())
	l -= 1
	r -= 1
	if a[r] != x:
		print(r + 1)
	elif prev[r] == -1 or prev[r] < l:
		print(-1)
	else:
		print(prev[r] + 1)


(n, m) = list(map(int, input().split()))
l = input().split()
(L, ans) = ([0 for i in range(n)], [])
L[0] = -1
for i in range(1, n):
	if l[i] == l[i - 1]:
		L[i] = L[i - 1]
	else:
		L[i] = i
for i in range(m):
	s = input().split()
	b = int(s[1])
	if l[b - 1] != s[2]:
		ans += [str(b)]
	elif L[b - 1] >= int(s[0]):
		ans += [str(L[b - 1])]
	else:
		ans += ['-1']
print('\n'.join(ans))


from sys import *

def input():
	return stdin.readline()
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
ans = []
difPre = [-1 for i in range(n)]
for i in range(1, n):
	if a[i] == a[i - 1]:
		difPre[i] = difPre[i - 1]
	else:
		difPre[i] = i - 1
for i in range(m):
	(l, r, x) = map(int, input().split())
	if a[r - 1] != x:
		ans.append(str(r))
	elif difPre[r - 1] >= l - 1:
		ans.append(str(difPre[r - 1] + 1))
	else:
		ans.append('-1')
print('\n'.join(ans))


import sys
(n, m) = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [n + 1] * (n + 1)
for i in range(n - 1, 0, -1):
	b[i] = i + 1 if a[i] != a[i + 1] else b[i + 1]
ans = [-1] * m
for i in range(m):
	(l, r, x) = map(int, sys.stdin.readline().split())
	if a[l] != x:
		ans[i] = l
	elif b[l] <= r:
		ans[i] = b[l]
print(*ans, sep='\n')


from itertools import combinations, accumulate, groupby, count
from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from os import *
from re import *
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer, end=''):
	stdout.write(str(answer) + end)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
(n, m) = zzz()
arr = zzz()
new = [0] * (n + 1)
for i in range(n - 2, -1, -1):
	if arr[i] == arr[i + 1]:
		new[i] = new[i + 1]
	else:
		new[i] = i + 1
res = [0] * m
for _ in range(m):
	(l, r, x) = zzz()
	ans = -1
	if arr[l - 1] != x:
		ans = l
	elif new[l - 1] != new[r - 1]:
		ans = new[l - 1] + 1
	res[_] = ans
for i in res:
	print(i)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	if i == 0 or a[i] != a[i - 1]:
		b.append(i)
	else:
		b.append(b[i - 1])
ans = []
for i in range(m):
	(l, r, x) = map(int, input().split())
	ans.append(r if a[r - 1] != x else b[r - 1] if b[r - 1] >= l else -1)
print('\n'.join(map(str, ans)))


(n, m) = [int(i) for i in input().split()]
a = input().split()
b = [0] * n
ans = []
for i in range(1, n):
	if a[i] != a[i - 1]:
		b[i] = i
	else:
		b[i] = b[i - 1]
for i in range(m):
	c = input().split()
	c[1] = int(c[1])
	c[0] = int(c[0])
	if a[c[1] - 1] != c[2]:
		ans.append(str(c[1]))
	elif b[c[1] - 1] <= c[0] - 1:
		ans.append(str(-1))
	else:
		ans.append(str(b[c[1] - 1]))
print('\n'.join(ans))


import sys
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
nxt = [0] * 1000005
nxt[n] = n
for i in range(n - 2, -1, -1):
	if a[i] != a[i + 1]:
		nxt[i + 1] = i + 1
	else:
		nxt[i + 1] = nxt[i + 2]
for _ in range(m):
	(l, r, x) = map(int, sys.stdin.readline().split())
	if a[l - 1] != x:
		print(l)
	elif nxt[l] < r:
		print(nxt[l] + 1)
	else:
		print(-1)


from sys import *
(n, m) = [int(t) for t in input().split()]
vec = []
pre = []
for (idx, val) in enumerate([int(t) for t in stdin.readline().split()]):
	vec.append(val)
	last = -1 if idx == 0 else idx - 1 if vec[idx - 1] != val else pre[idx - 1]
	pre.append(last)
ans = []
for q in range(m):
	(l, r, x) = [int(t) for t in stdin.readline().split()]
	l -= 1
	r -= 1
	if vec[l] == x and vec[r] == x:
		ans.append(-1 if pre[r] < l else pre[r] + 1)
	else:
		ans.append(l + 1 if vec[l] != x else r + 1)
print('\n'.join([str(t) for t in ans]))


from sys import stdin
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in stdin.readline().split()]
re = []
prev = [-1 for i in range(n)]
for i in range(1, n):
	if a[i] != a[i - 1]:
		prev[i] = i - 1
	else:
		prev[i] = prev[i - 1]
for _ in range(m):
	(l, r, x) = [int(i) for i in stdin.readline().split()]
	i = r - 1
	if a[i] != x:
		re.append(str(i + 1))
	elif prev[i] < l - 1:
		re.append('-1')
	else:
		re.append(str(prev[i] + 1))
print('\n'.join(re))


from sys import stdin
(n, m) = [int(i) for i in stdin.readline().split()]
ori = [int(i) for i in stdin.readline().split()]
pre = [-1] * n
ans = list()
for i in range(n - 1):
	if ori[i] != ori[i + 1]:
		pre[i + 1] = i
	else:
		pre[i + 1] = pre[i]
for i in range(m):
	(l, r, x) = [int(i) for i in stdin.readline().split()]
	tem = r - 1
	if ori[tem] != x:
		ans.append(str(r))
	elif pre[tem] < l - 1:
		ans.append('-1')
	else:
		ans.append(str(pre[tem] + 1))
print('\n'.join(ans))


from sys import stdin
(n, m) = list(map(int, stdin.readline().split()))
a = list(map(int, stdin.readline().split()))
pre = []
(t, index) = (a[0], 0)
for i in range(n):
	index = index if a[i] == t else i
	t = a[i]
	pre.append(index)
prt = []
for i in range(m):
	(l, r, x) = list(map(int, stdin.readline().split()))
	L = pre[r - 1]
	if a[r - 1] == x:
		sl = pre[r - 1] + 1
		if sl <= l:
			prt.append(str(-1))
			continue
		r = sl - 1
	prt.append(str(r))
print('\n'.join(prt))


from sys import stdin, stdout

def main():
	(n, m) = map(int, stdin.readline().split())
	ar = list(map(int, stdin.readline().split()))
	left = [0] * n
	left[0] = -1
	cl = -1
	for i in range(1, n):
		if ar[i] != ar[i - 1]:
			cl = i
		left[i] = cl
	for _ in range(m):
		(l, r, val) = map(int, stdin.readline().split())
		if ar[r - 1] != val:
			stdout.write(str(r))
		elif left[r - 1] >= l:
			stdout.write(str(left[r - 1]))
		else:
			stdout.write('-1')
		stdout.write('\n')
main()


import io
import sys

def main(args):
	ifs = io.StringIO(sys.stdin.read())
	(n, m) = list(map(int, ifs.readline().split()))
	a = list(map(int, ifs.readline().split()))
	b = [0] * len(a)
	c = [0] * len(a)
	for i in range(1, n):
		if a[i] == a[i - 1]:
			b[i] = b[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if a[i] == a[i + 1]:
			c[i] = c[i + 1] + 1
	for i in range(m):
		(L, R, x) = list(map(int, ifs.readline().split()))
		(L, R) = (L - 1, R - 1)
		if a[L] != x:
			print(L + 1)
			continue
		if a[R] != x:
			print(R + 1)
			continue
		left = L + c[L] + 1
		if left <= R:
			print(left + 1)
			continue
		right = R - b[R] - 1
		if L <= right:
			print(right + 1)
			continue
		print(-1)
ofs = io.StringIO()
sys.stdout = ofs
status = main(sys.argv)
sys.__stdout__.write(ofs.getvalue())
sys.exit(status)


(n, m) = map(int, input().split())
a = input().split()
p = [0 for i in range(n)]
p[0] = -1
ans = []
for i in range(1, n):
	if a[i] == a[i - 1]:
		p[i] = p[i - 1]
	else:
		p[i] = i - 1
for i in range(m):
	s = input().split()
	r = int(s[1])
	if a[r - 1] != s[2]:
		ans += [str(r)]
	elif p[r - 1] >= int(s[0]) - 1:
		ans += [str(p[r - 1] + 1)]
	else:
		ans += ['-1']
print('\n'.join(ans))


(n, m) = [int(i) for i in input().split()]
a = input().split()
result = []
prev = [-1] * n
for i in range(1, n):
	if a[i] != a[i - 1]:
		prev[i] = i - 1
	else:
		prev[i] = prev[i - 1]
for i in range(m):
	(l, r, x) = input().split()
	r = int(r)
	if a[r - 1] != x:
		answer = r
	elif prev[r - 1] < int(l) - 1:
		answer = -1
	else:
		answer = prev[r - 1] + 1
	result.append(str(answer))
print('\n'.join(result))


import sys
input = sys.stdin.buffer.readline

def print(val):
	sys.stdout.write(str(val) + '\n')

def prog():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split())) + [-1]
	intervals = [[-1, -1]]
	for i in range(n):
		if a[i] != a[i + 1]:
			intervals.append([intervals[-1][1] + 1, i])
	for q in range(m):
		(l, r, x) = map(int, input().split())
		l -= 1
		r -= 1
		L = 0
		R = len(intervals) - 1
		while L != R:
			m = (L + R + 1) // 2
			if intervals[m][0] > l:
				R = m - 1
			else:
				L = m
		if a[intervals[L][0]] != x:
			print(l + 1)
		elif L + 1 < len(intervals) and intervals[L + 1][0] <= r:
			print(intervals[L + 1][0] + 1)
		else:
			print(-1)
prog()


(n, m) = tuple(map(int, input().split()))
li = input().split()
a = [0] * n
for i in range(1, n):
	if li[i] != li[i - 1]:
		a[i] = i
	else:
		a[i] = a[i - 1]
result = [0] * m
for k in range(m):
	(l, r, x) = input().split()
	(l, r) = (int(l), int(r))
	if li[r - 1] != x:
		result[k] = str(r)
	elif a[r - 1] >= l:
		result[k] = str(a[r - 1])
	else:
		result[k] = '-1'
print('\n'.join(result))


from sys import stdin
(n, m) = [int(i) for i in stdin.readline().split()]
a = [int(i) for i in stdin.readline().split()]
b = [None] * n
b[0] = -1
ans = [None] * m
for i in range(1, len(a)):
	if a[i] == a[i - 1]:
		b[i] = b[i - 1]
	else:
		b[i] = i - 1
for i in range(m):
	(l, r, x) = [int(j) for j in stdin.readline().split()]
	k = r - 1
	if a[k] != x:
		ans[i] = str(k + 1)
	elif b[k] + 1 >= l:
		ans[i] = str(b[k] + 1)
	else:
		ans[i] = '-1'
print('\n'.join(ans))


import sys

def preprocess(arr):
	left_i = -1
	prev = arr[0]
	preprocessed = []
	for (i, k) in enumerate(arr):
		if prev != k:
			prev = k
			left_i = i
		preprocessed.append(left_i)
	return preprocessed

def query(arr, pre, l, r, x):
	if arr[r - 1] != x:
		return r
	if pre[r - 1] >= l:
		return pre[r - 1]
	return -1

def main():
	(n, m) = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().split()))
	pre = preprocess(arr)
	for _ in range(m):
		(l, r, x) = map(int, sys.stdin.readline().split())
		print(query(arr, pre, l, r, x))
main()


import sys

def preprocess(arr):
	left_i = -1
	prev = arr[0]
	preprocessed = []
	for (i, k) in enumerate(arr):
		if prev != k:
			prev = k
			left_i = i
		preprocessed.append(left_i)
	return preprocessed

def query(arr, pre, l, r, x):
	if arr[r - 1] != x:
		return r
	if pre[r - 1] >= l:
		return pre[r - 1]
	return -1

def solve():
	(n, m) = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().split()))
	pre = preprocess(arr)
	for _ in range(m):
		(l, r, x) = map(int, sys.stdin.readline().split())
		yield str(query(arr, pre, l, r, x))

def main():
	sys.stdout.write('\n'.join(solve()))
main()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = [N + 1 for _ in range(N)]
idx = N + 1
for i in range(N - 1)[::-1]:
	if A[i] != A[i + 1]:
		idx = i + 1
	B[i] = idx
res = []
for _ in range(M):
	(l, r, x) = map(int, input().split())
	if A[l - 1] != x:
		res.append(l)
	elif B[l - 1] <= r - 1:
		res.append(B[l - 1] + 1)
	else:
		res.append(-1)
print('\n'.join(map(str, res)))


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(b, c) = ([0], [])
now = 0
for j in range(n - 1):
	if a[j] ^ a[j + 1]:
		now += 1
		c.append(j)
	b.append(now)
c.append(n)
for _ in range(m):
	(l, r, p) = map(int, input().split())
	x = c[b[l - 1]]
	y = x + 1
	if a[l - 1] ^ p:
		ans = l
	elif y >= r:
		ans = -1
	else:
		ans = x + 1 if a[x] ^ p else y + 1
	print(ans)


from sys import stdin, stdout
(n, m) = map(int, input().split())
a = [0]
a.extend(list(map(int, stdin.readline().split())))
a[0] = a[1] + 1
p = list(range(n + 1))
(i, j) = (n, n)
while i > 0:
	while a[i] == a[j] and j >= 0:
		j -= 1
	for k in range(j + 1, i + 1):
		p[k] = j
	i = j
for _ in range(m):
	(l, r, x) = map(int, stdin.readline().split())
	if a[r] != x:
		stdout.write(str(r))
	elif p[r] >= l:
		stdout.write(str(p[r]))
	else:
		stdout.write('-1')
	stdout.write('\n')


from sys import stdin
_data = iter(stdin.read().split('\n'))

def input():
	while True:
		return next(_data)
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
ans = []
difPre = [-1 for i in range(n)]
for i in range(1, n):
	if a[i] == a[i - 1]:
		difPre[i] = difPre[i - 1]
	else:
		difPre[i] = i - 1
for i in range(m):
	(l, r, x) = map(int, input().split())
	if a[r - 1] != x:
		ans.append(str(r))
	elif difPre[r - 1] >= l - 1:
		ans.append(str(difPre[r - 1] + 1))
	else:
		ans.append('-1')
print('\n'.join(ans))


from collections import defaultdict
import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(n):
	if i == 0 or a[i] != a[i - 1]:
		b.append(i)
	else:
		b.append(b[i - 1])
ans = []
for i in range(m):
	(l, r, x) = map(int, input().split())
	ans.append(r if a[r - 1] != x else b[r - 1] if b[r - 1] >= l else -1)
print('\n'.join(map(str, ans)))


from itertools import combinations, accumulate, groupby, count
from sys import stdout, stdin, setrecursionlimit
from collections import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (input, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer, end=''):
	stdout.write(str(answer) + end)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
(n, m) = zzz()
arr = zzz()
new = [0] * (n + 1)
for i in range(n - 2, -1, -1):
	if arr[i] == arr[i + 1]:
		new[i] = new[i + 1]
	else:
		new[i] = i + 1
res = [0] * m
for _ in range(m):
	(l, r, x) = zzz()
	ans = -1
	if arr[l - 1] != x:
		ans = l
	elif new[l - 1] != new[r - 1]:
		ans = new[l - 1] + 1
	res[_] = ans
for i in res:
	output(i, end='\n')


__author__ = 'Utena'
from sys import *

def input():
	return stdin.readline()
(n, m) = map(int, input().split())
ans1 = []
prev = [-1 for i in range(n)]
s = input().split()
for i in range(1, n):
	if s[i] != s[i - 1]:
		prev[i] = i - 1
		now = i
	else:
		prev[i] = prev[i - 1]
for j in range(m):
	(l, r, x) = input().split()
	(l, r) = (int(l), int(r))
	if s[r - 1] != x:
		ans = r
	elif prev[r - 1] < l - 1:
		ans = -1
	else:
		ans = prev[r - 1] + 1
	ans1.append(str(ans))
print('\n'.join(ans1))


from sys import stdin
(n, m) = [int(i) for i in input().split()]
l = [int(i) for i in stdin.readline().split()]
prev = [-1 for i in range(n)]
re = []
for i in range(n - 1):
	if l[i] != l[i + 1]:
		prev[i + 1] = i
	else:
		prev[i + 1] = prev[i]
for _ in range(m):
	(le, ri, xi) = [int(i) for i in stdin.readline().split()]
	i = ri - 1
	if l[i] != xi:
		re.append(str(ri))
	elif prev[i] < le - 1:
		re.append('-1')
	else:
		re.append(str(prev[i] + 1))
print('\n'.join(re))


import collections
import math
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
(ans, f) = ([], [0] * n)
f[0] = -1
for i in range(1, n):
	if A[i] != A[i - 1]:
		f[i] = i - 1
	else:
		f[i] = f[i - 1]
for i in range(m):
	(l, r, x) = map(int, input().split())
	if A[r - 1] != x:
		ans.append(r)
	elif f[r - 1] >= l - 1:
		ans.append(f[r - 1] + 1)
	else:
		ans.append(-1)
print('\n'.join((str(x) for x in ans)))


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve():
	(n, k) = li()
	l = li()
	leftind = [-1] * n
	for i in range(1, n):
		if l[i] != l[i - 1]:
			leftind[i] = i - 1
		else:
			leftind[i] = leftind[i - 1]
	for i in range(k):
		(left, right, x) = li()
		y = leftind[right - 1]
		left -= 1
		right -= 1
		if right == 0:
			if l[right] == x:
				print(-1)
			else:
				print(1)
			continue
		if l[right] != x:
			print(right + 1)
			continue
		if left <= y <= right:
			print(y + 1)
			continue
		print(-1)
t = 1
for _ in range(t):
	solve()


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
(n, m) = zzz()
arr = zzz()
new = [0] * (n + 1)
for i in range(n - 2, -1, -1):
	if arr[i] == arr[i + 1]:
		new[i] = new[i + 1]
	else:
		new[i] = i + 1
for _ in range(m):
	(l, r, x) = zzz()
	l -= 1
	r -= 1
	ans = -1
	if arr[l] != x:
		ans = l + 1
	elif new[l] != new[r]:
		ans = new[l] + 1
	print(ans)


def solver(ifs):
	(n, m) = tuple(map(int, ifs.readline().split()))
	a = tuple(map(int, ifs.readline().split()))
	b = [0] * len(a)
	c = [0] * len(a)
	for i in range(1, n):
		if a[i] == a[i - 1]:
			b[i] = b[i - 1] + 1
	for i in range(n - 2, -1, -1):
		if a[i] == a[i + 1]:
			c[i] = c[i + 1] + 1
	for i in range(m):
		(L, R, x) = tuple(map(int, ifs.readline().split()))
		(L, R) = (L - 1, R - 1)
		left = L + c[L] + 1
		right = R - b[R] - 1
		res = -1
		if a[L] != x:
			res = L + 1
		elif a[R] != x:
			res = R + 1
		elif left <= R:
			res = left + 1
		elif L <= right:
			res = right + 1
		print(res)

def main():
	import sys
	if sys.version_info.major == 3:
		from io import StringIO as StreamIO
	else:
		from io import BytesIO as StreamIO
	with StreamIO(sys.stdin.read()) as ifs, StreamIO() as ofs:
		_stdout = sys.stdout
		sys.stdout = ofs
		solver(ifs)
		sys.stdout = _stdout
		sys.stdout.write(ofs.getvalue())
	return 0
main()


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
B = [-1]
for i in range(1, n):
	if A[i] == A[i - 1]:
		B.append(B[-1])
	else:
		B.append(i - 1)
ans = []
for _ in range(m):
	(l, r, x) = map(int, input().split())
	l -= 1
	r -= 1
	if A[r] != x:
		ans.append(r + 1)
	elif B[r] >= l:
		ans.append(B[r] + 1)
	else:
		ans.append(-1)
print('\n'.join(list(map(str, ans))))