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.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {
	
	static int [] A;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        
        int a = in.nextInt();
        int m = in.nextInt();
        A = new int[a+1];
        int [] S = new int[a + 1];

        for( int i = 1; i <= a; ++i ){
        	A[i - 1] = in.nextInt();
        	S[i] = S[i - 1] + A[i - 1];
        }
   
        
        int lg = 1;
        
        while( ( 1 << lg) <= a ) ++lg;
        int [][] T = new int[a+1][lg];
        
        for( int i = 0; i < a; ++i )
        	T[i][0] = A[i];
        
        //i + 2^(j-1) 
        
        for( int i = 1; i <= lg; ++i )
        	for( int j = 0; j <= a - ( 1 << i ); ++j )
        		T[j][i] = Math.max( T[j][i - 1], T[ j + (1 << (i - 1))][i-1] );
        
        for( int j = 0; j < m; ++j ){
        	int l = in.nextInt();
        	int r = in.nextInt();
        	int v = in.nextInt();

    		int ini = l;
    		int fin = r;
    		int s = 0;
 
    		while( ini < fin ){
    			
    			int md = (ini + fin) / 2;
     			s = S[md] - S[ini - 1];
     			
     			int sm = (md - ini + 1) * v;
     			int exp = (int) (Math.log10(md - ini + 1) / Math.log10(2.0));
     			
     			int k = Math.max( T[ini-1][exp], T[ md - ( 1 << exp)][exp] );
     			
     			if( s != sm || ( s == sm && k != v) ) //|| ( s == sm && query( 0, a - 1, ini - 1, md - 1, 1 ) != v ) )
     				fin = md;
     			else
     				ini = md + 1;
    		}
    		out.println( ( A[fin - 1] == v ) ? -1 : fin );
        }
        out.close();
	}
	
	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        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 int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

	}

}