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

Difficulty: interview

Starter code:

Solutions:
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())
    #q.append([l - 1, r - 1, x])
    #for i in range(m):
    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))

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))
    else:
        if difPre[r-1]>=l-1:
            ans.append(str(difPre[r-1]+1))
        else:
            ans.append('-1')
print('\n'.join(ans))

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))


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))

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 

n,m=map(int,stdin.readline().split())
a=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=stdin.readline().split()
    l,r=int(l),int(r)
    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))

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))

n,m = map(int,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))

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)]
    else:
        if 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()
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))


# -*- coding: utf-8 -*-
"""
Created on Tue May 17 15:26:55 2016

@author: Alex
"""
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))
    else:
        if prev[i]<le-1:
            re.append('-1')
        else:
            re.append(str(prev[i]+1))
print('\n'.join(re))
        



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])
#print(a)
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))

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()]
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))
	else:
		if pre[tem] < l-1:
			ans.append('-1')
		else:
			ans.append(str(pre[tem]+1))

print('\n'.join(ans))

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))
	else:
		if pre[r-1] == pre[l-1]:
			ans.append('-1')
			continue
		else:
			ans.append(str(pre[r-1]+1))

print('\n'.join(ans))

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))