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:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class CEdu7 {
	static int[] input;
	public static void main(String[] args) {
		MyScanner scan = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		N = scan.nextInt();int Q = scan.nextInt();
		logmax = (int)Math.ceil(Math.log(N)/Math.log(2.));	
		rMaxQ = new int[logmax+1][N+1];
		int[] list = new int[N+1];
		long[] sum = new long[N+1];
		for(int i=1;i<=N;i++){
			list[i] = scan.nextInt();
			sum[i] = sum[i-1]+list[i];
		}
		input = new int[N];
		for(int i=1;i<=N;i++)input[i-1]=list[i];
		gen();
		
		for(int q=0;q<Q;q++){
			int l = scan.nextInt(), r = scan.nextInt(), x = scan.nextInt();
			
			while(l<=r){
				
				if(input[max(l-1,r-1)]==x&&sum[r]-sum[l-1]==(r-l+1)*x){
					l=-1;
					break;
				}
				if(l==r)
					break;
				int mid = l+r>>1;
				
				long lsum = sum[mid]-sum[l-1];// l .. mid
				long rsum = sum[r]-sum[mid]; //mid+1 ... r
				if(lsum!=(long)(mid-l+1)*(long)x||input[max(l-1,mid-1)]!=x){
					r=mid;
				}else{
					l = mid+1;
				}
			}
			out.println(l);
			
		}
		out.close();
	}
	
	private static int max(int i, int j){
		int k = (int)(Math.log(j-i+1)/Math.log(2.0));
		if(input[rMaxQ[k][i]] >= input[rMaxQ[k][j-(1<<k)+1]])return rMaxQ[k][i];
		else return rMaxQ[k][j-(1<<k)+1];
	}
	static int N;
	static int logmax;
	static int[][] rMaxQ;
	public static void gen() {
		for(int i=0;i<N;i++){rMaxQ[0][i]=i;}
		for(int j=1; 1<<j <= N; j++){
			for (int i=0; i + (1<<j)-1 < N; i++){
				//<= and >= gives first occurance :: < and > gives last
				if (input[rMaxQ[j-1][i]] > input[rMaxQ[j-1][i+(1<<(j-1))]])rMaxQ[j][i]=rMaxQ[j-1][i];
				else rMaxQ[j][i] = rMaxQ[j-1][i+(1<<(j-1))];
			}
		}
	}
	private static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner()  {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next(){
			while(st==null||!st.hasMoreElements()){
				try{st = new StringTokenizer(br.readLine());}
				catch(IOException e){e.printStackTrace();}
			}return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong(){return Long.parseLong(next());}
		double nextDouble(){return Double.parseDouble(next());}
	}
}