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.*;
import java.util.*;
   
public class Main {
    static Scanner in = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);
    static StreamTokenizer inst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

	 static int nextInt() throws IOException
	   {
	      inst.nextToken();
	      return (int)inst.nval;
	   }
    public static void main(String args[]) throws IOException {
    	int n =nextInt();
    	int m=nextInt();
    	int a[]=new int[n];
    	int d[]=new int[n];
    	for(int i=0;i<n;i++) {
    		a[i]=nextInt();
    		d[i]=-1;
    	}
    	int i1=0;
    	int i2=-1;	
    	for(int i=1;i<n;i++) {
//    		System.out.print(a[i]+" "+i1+" "+i2);
    		if(i2==-1&&a[i1]!=a[i]) {   			
    			i2=i1;
    			i1=i;
    		}else if(a[i]==a[i1]) {
    			i1=i;
    		}else{
    			i2=i1;
    			i1=i;
    		}
    		if(i2!=-1) {
    			if(a[i]!=a[i2])
    			d[i]=i2;
    		}
 //   		System.out.println(" "+i1+" "+i2);
    	}
//    	for(int i=0;i<n;i++) {
//    		System.out.print(a[i]+" ");
//    	}
//    	System.out.println();
//    	for(int i=0;i<n;i++) {
//    		System.out.print(d[i]+" ");
//    	}
//    	System.out.println();
    	int ans[] = new int[m];
    	for(int i=0;i<m;i++) {
    		int l =nextInt();
    		int r =nextInt();
    		int x =nextInt();
    		int c = d[r-1];
    		if(a[r-1]!=x) {
    			ans[i]=r;
    		}else if(c==-1) {
    			ans[i]=-1;
    		}else if(a[c]!=x&&c>=l-1){
    			ans[i]=c+1;
    		}else {
    			ans[i]=-1;
    		}
    	}
    	for(int i=0;i<m;i++) {
    		out.println(ans[i]);
    	}
    	out.close();
    }
}