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:
/*
     * Code Author: Akshay Miterani
     * DA-IICT
     */
    import java.io.*;
    import java.util.*;
    
     
    public class MainY {
     
    	static double eps=(double)1e-6;
    	static long mod=(int)1e9+7;
    	static boolean f=true;
    	public static void main(String args[]){
    		InputReader in = new InputReader(System.in);
    		OutputStream outputStream = System.out;
    		PrintWriter out = new PrintWriter(outputStream);
    		//----------My Code Starts Here----------
    		int n=in.nextInt();
    		int m=in.nextInt();
    		int a[]=new int[n];
    		for(int i=0;i<n;i++){
    			a[i]=in.nextInt();
    		}
    		int up[]=new int[n+1];
    		up[n-1]=Integer.MAX_VALUE;
    		for(int i=n-2;i>=0;i--){
    			if(a[i]!=a[i+1]){
    				up[i]=i+1;
    			}
    			else{
    				up[i]=up[i+1];
    			}
    		}
    		//for(int i=0;i<n;i++)
    			//System.out.print(up[i]+" ");
    		for(int k=0;k<m;k++){
    			int l=in.nextInt()-1;
    			int r=in.nextInt()-1;
    			int x=in.nextInt();
    			if(a[l]!=x){
    				out.println(l+1);
    			}
    			else{
    				if(up[l]<=r){
    					out.println(up[l]+1);
    				}
    				else{
    					out.println("-1");
    				}
    			}
    		}
    		out.close();
    		//---------------The End------------------
    	}
    	
    	static class Pair implements Comparable<Pair>{
    		int x;
    		int y;
    		int p,t;
    		Pair(int xx){
    			x=xx;
    			//y=yy;
    		}
    		@Override
    		public int compareTo(Pair o) {
    			if(f)
					return Long.compare((this.p),(o.p));
				else
					return Long.compare((this.t),(o.t));
    		}
    	}
    	
    	static class InputReader {
    	    public BufferedReader reader;
    	    public StringTokenizer tokenizer;
     
    	    public InputReader(InputStream inputstream) {
    	      reader = new BufferedReader(new InputStreamReader(inputstream));
    	      tokenizer = null;
    	    }
    	    
    	    public String nextLine(){
    	    	String fullLine=null;
    	    	while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    	            try {
    	              fullLine=reader.readLine();
    	            } catch (IOException e) {
    	              throw new RuntimeException(e);
    	            }
    	            return fullLine;
    	          }
    	          return fullLine;
    	    }
    		public String next() {
    	      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    	        try {
    	          tokenizer = new StringTokenizer(reader.readLine());
    	        } catch (IOException e) {
    	          throw new RuntimeException(e);
    	        }
    	      }
    	      return tokenizer.nextToken();
    	    }
    		public long nextLong() {
    		      return Long.parseLong(next());
    		    }
    	    public int nextInt() {
    	      return Integer.parseInt(next());
    	    }
    	  }
    }