Problem: You are given array a with n integers and m queries. The i-th query is given with three integers li, ri, xi.

For the i-th query find any position pi (li ≤ pi ≤ ri) so that api ≠ xi.

Input

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 ai (1 ≤ ai ≤ 106) — the elements of the array a.

Each of the next m lines contains three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106) — the parameters of the i-th query.

Output

Print m lines. On the i-th line print integer pi — the position of any number not equal to xi in segment [li, ri] 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

Solution (in JAVA):

Solution:
//package GeneralProblems;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.StringTokenizer;

public class NotEqualOnASegment {
	static class pair{
		int min, max;
		public pair(int min, int max) {
			this.min=min;
			this.max= max;
		}
	}
	static class SegmentTree {		// 1-based DS, OOP
		
		int N; 			//the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array;
		pair [] sTree;
		SegmentTree(int[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new pair[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
			build(1,1,N);
		}
		
		void build(int node, int b, int e)	// O(n)
		{
			if(b == e)					
				sTree[node] = new pair(b,b);
			else						
			{
				int mid = b + e >> 1;
				build(node<<1,b,mid);
				build(node<<1|1,mid+1,e);
				int min1 = array[sTree[node<<1].min];
				int min2 = array[sTree[node<<1|1].min];
				int minAns = -1;
				if(min1<min2)
					minAns = sTree[node<<1].min;
				else
					minAns = sTree[node<<1|1].min;
				int max1 = array[sTree[node<<1].max];
				int max2 = array[sTree[node<<1|1].max];
				int maxAns = -1;
				if(max1<max2)
					maxAns = sTree[node<<1|1].max;
				else
					maxAns = sTree[node<<1].max;
				sTree[node] = new pair(minAns,maxAns);
			}
		}
		
		
		
		pair query(int i, int j)
		{
			return query(1,1,N,i,j);
		}
		
		pair query(int node, int b, int e, int i, int j)	// O(log n)
		{
			if(i>e || j <b)
				return new pair(0,0);		
			if(b>= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			pair q1 = query(node<<1,b,mid,i,j);
			pair q2 = query(node<<1|1,mid+1,e,i,j);
			int min1 = array[q1.min];
			int min2 = array[q2.min];
			int minAns = -1;
			if(min1==0)
				min1 =(int)1e9;
			if(min2==0)
				min2 =(int)1e9;
			if(min1<min2)
				minAns = q1.min;
			else
				minAns = q2.min;
			int max1 = array[q1.max];
			int max2 = array[q2.max];
			int maxAns = -1;
			if(max1<max2)
				maxAns = q2.max;
			else
				maxAns = q1.max;
			return new pair(minAns,maxAns);
//			return new pair(Math.min(q1.min, q2.min),Math.max(q1.max,q2.max));	
					
		}
		
		
	
	}

public static void main(String[] args) throws IOException {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(in.readLine());
	int n = Integer.parseInt(st.nextToken()), m= Integer.parseInt(st.nextToken());
	int N = 1; while(N < n) N <<= 1; //padding
	st = new StringTokenizer(in.readLine());
	int[] arr= new int[N + 1];
	for(int i = 1; i <= n; i++)
		arr[i] = Integer.parseInt(st.nextToken());
	
	SegmentTree sg = new SegmentTree(arr);
	
	PrintWriter out= new PrintWriter(System.out);
	while(m-->0) {
		st =new StringTokenizer(in.readLine());
		int l = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int val = Integer.parseInt(st.nextToken());
		pair cur = sg.query(l, r);
//		System.out.println(cur.min+" "+cur.max);
		if(arr[cur.min]==val&&arr[cur.max]==val)
			out.println(-1);
		else
			if(arr[cur.min]==val)
				out.println(cur.max);
			else
				out.println(cur.min);
	}
	out.flush();
	out.close();
}
}