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.*;
import java.lang.*;
import java.math.BigInteger;
import java.util.Map.Entry;
import java.util.logging.Level;
import java.util.logging.Logger;


public class Main
{
    static StringTokenizer st=new StringTokenizer("");
    static BufferedReader br;
    
    ///////////////////////////////////////////////////////////////////////////////////
    
    
    public static void main(String args[]) throws FileNotFoundException, IOException, Exception
    {
        //Scanner class
        //Scanner in =new Scanner(new FileReader("input.txt"));
        //Scanner in=new Scanner(System.in);
        
        //PrintWriter out = new PrintWriter(new FileWriter("output.txt"));
        //br=new BufferedReader(new FileReader("input.txt"));
        
        br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        
        //StringTokenizer st;//=nedsw StringTokenizer(br.readLine());
        //////////////////////////////////////////////////////////////////////////////////////
        
        int n=ni(),q=ni();
        int arr[]=new int[n+1];
        for(int i=1;i<=n;i++) arr[i]=ni();
        int next[]=new int[n+1];
        next[n]=-1;
        for(int i=n-1;i>0;i--)
        {
            if(arr[i]!=arr[i+1])
                next[i]=i+1;
            else next[i]=next[i+1];
        }
        for(int i=0;i<q;i++)
        {
            int l=ni(),r=ni(),x=ni();
            if(arr[l]!=x) out.println(l);
            else if(next[l]>r) out.println(-1);
            else out.println(next[l]);
        }
        
        //////////////////////////////////////////////////////////////////////////////////////
	out.close();
    }
    
    
    
    
    ///////////////////////////////////////////////////////////////////////////////
    
    private static long gcd(long a,long b)
    {
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
    private static class pair implements Comparable<pair>
    {
        int first;
        int second;
        pair()
        {
            first=0;
            second=0;
        }
        pair(int f,int s)
        {
            first=f;
            second=s;
        }

        public int compareTo(pair o)
        {
            if(second >  o.second)
                return 1;
            else if(second < o.second)
                return -1;
            else
                return 0;
        }
    }
    
    public static Integer ni() throws Exception
    {
        if(!st.hasMoreTokens())
            st=new StringTokenizer(br.readLine());
        return Integer.parseInt(st.nextToken());
    }
    public static BigInteger nb()throws Exception
    {
        if(!st.hasMoreElements())
            st=new StringTokenizer(br.readLine());
        return BigInteger.valueOf(Long.parseLong(st.nextToken()));
    }
    public static Long nl() throws Exception
    {
        if(!st.hasMoreTokens())
            st=new StringTokenizer(br.readLine());
        return Long.parseLong(st.nextToken());
    }
    public static Double nd()throws Exception
    {
        if(!st.hasMoreElements())
            st=new StringTokenizer(br.readLine());
        return Double.parseDouble(st.nextToken());
    }
    public static String ns()throws Exception
    {
        if(!st.hasMoreElements())
            st=new StringTokenizer(br.readLine());
        return st.nextToken();
    }
}