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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;
public class cfvc13_temp
{
	static BufferedReader reader;
    static StringTokenizer tokenizer;
    static void init(InputStream input) 
    {
        reader = new BufferedReader( new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
    static String next() throws IOException
    {
        while ( ! tokenizer.hasMoreTokens() )
        {
            tokenizer = new StringTokenizer(reader.readLine() );
        }
        return tokenizer.nextToken();
    }
 
    static long nextInt() throws IOException 
    {
        return Long.parseLong( next() );
    }
	static PrintWriter writer;
	static void outit(OutputStream outputStream)
	{
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}
	static void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}
 
	static void println(Object...objects) {
		print(objects);
		writer.println();
	}
 
	static void close() {
		writer.close();
	}
 
	static void flush() {
		writer.flush();
	}
    public static void main(String [] args) throws IOException
    {
    	init(System.in) ;
    	outit(System.out) ;
//    	int t = (int) nextInt() ;
//    	for(int i =0 ; i<t ; i++)
    	output() ;
        flush();
        close();
    }
    static long mod = 1000000007 ;
    public static void output() throws IOException
    {
    	int n = (int) nextInt() ;
    	int m = (int) nextInt() ;
    	int [] a = new  int [n] ;
    	for(int i = 0 ; i<n ; i++)
    	{
    		a[i] = (int) nextInt() ;
    	}
    	int [] p = new int [n] ;
    	p[0] = -1 ;
    	for(int i = 1; i<n ; i++)
    	{
    		if(a[i]!=a[i-1])
    		{
    			p[i] = i-1 ;
    		}
    		else
    		{
    			p[i] = p[i-1] ;
    		}
    	}
    	for(int i = 0 ;i<m ; i++)
    	{
    		int l = ((int) nextInt()-1);
    		int r = ((int) nextInt()-1);
    		int x = (int) nextInt() ;
    		if(a[r]!=x)
    		{
    			println((r+1)) ;
    		}
    		else
    		{
    			if(p[r]>=l)
    			{
    				if(p[r]!=-1)
    				{
    				println(p[r]+1) ;
    				}
    				else
    				{
    					println(-1) ;
    				}
    			}
    			else
    			{
    				println(-1) ;
    			}
    		}
    	}
    	
    }
}