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.util.*;  
import java.math.*;  
import java.io.*;


public class Main {  
    public static void main(String[] args) { 
        InputStream inputStream = System.in;  
        OutputStream outputStream = System.out;  
        Scanner in = new Scanner(inputStream);  
        PrintWriter out = new PrintWriter(outputStream);  
        solve(in, out);  
        out.close();  
    }  
    
    static int[] a;
    static int m, n;

    static void solve(Scanner in, PrintWriter out) {  
    	n = in.nextInt();
    	m = in.nextInt();
    	a = new int[n + 2];
    	int []dp = new int[n + 2];
    	for(int i = 1; i <= n; i++) a[i] = in.nextInt();
    	for(int i = n; i >= 1; i --) { 
    		if(a[i + 1] == a[i]) dp[i] = dp[i + 1];
    		else dp[i] = i;
    	}
    	for(int i = 1; i <= m; i ++) {
    		int L = in.nextInt();
    		int R = in.nextInt();
    		int K = in.nextInt();
    		if(dp[L] >= R && a[L] == K) out.println("-1");
    		else if(a[L] != K) out.println(L);
    		else out.println(dp[L] + 1);
    	}
    }  
    
    static class Comp implements Comparator {
    	public int compare(Object x, Object y) {
    		return ((pii) x).X - ((pii) y).X;
    	}
    }
    
    
    static class pii {
    	int X, Y;
    	pii(int X, int Y) {
    		this.X = X;
    		this.Y = Y;
    	}
    }

    static class Scanner {    
        BufferedReader br;    
        StringTokenizer st;    
                
        public Scanner(InputStream in) {  
            br = new BufferedReader(new InputStreamReader(in));  
            eat("");  
        }   
          
        private void eat(String s) {    
            st = new StringTokenizer(s);  
        }    
        
        public String nextLine() {    
            try {    
                return br.readLine();    
            } catch (IOException e) {    
                return null;    
            }    
        }    
        
        public boolean hasNext() {    
            while (!st.hasMoreTokens()) {    
                String s = nextLine();    
                if (s == null)    
                return false;    
                eat(s);    
            }    
            return true;    
        }    
        
        public String next() {    
            hasNext();    
            return st.nextToken();    
        }    
        
        public int nextInt() {    
            return Integer.parseInt(next());    
        }    
            
        public long nextLong() {    
            return Long.parseLong(next());    
        }    
                
        public double nextDouble() {    
            return Double.parseDouble(next());    
        }    
            
        public BigInteger nextBigInteger() {    
            return new BigInteger(next());    
        }    
            
            
    }    
}