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:
/*      MOHD SADIQ        */


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.util.ArrayList;

public class Main {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private long longVal() throws IOException{
        return Long.parseLong(br.readLine().trim());
    }
    private int intVal() throws IOException{
        return Integer.parseInt(br.readLine().trim());
    }
    private double doubleVal() throws IOException{
        return Double.parseDouble(br.readLine().trim());
    }
    private int[] intArr() throws IOException{
        String[] s = br.readLine().trim().split(" ");
        int n = s.length;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(s[i]);
        }
        return a;
    }
    private long[] longArr() throws IOException {
        String[] s = br.readLine().trim().split(" ");
        int n = s.length;
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(s[i]);
        }
        return a;
    }
    private double[] doubleArr() throws IOException {
        String[] s = br.readLine().trim().split(" ");
        int n = s.length;
        double[] a = new double[n];
        for (int i = 0; i < n; i++) {
            a[i] = Double.parseDouble(s[i]);
        }
        return a;
    }
    private String[] stringArr() throws IOException{
        String[] s = br.readLine().trim().split(" ");
        return s;
    }
    private char[] charArr() throws IOException{
        return br.readLine().trim().toCharArray();
    }
    public static boolean[] sieve(int n){
        boolean[] primes = new boolean[n + 1];
        int i;
        Arrays.fill(primes,true);
        for(i = 2; i * i <= n; ++i) {
            if (primes[i]) {
                for(int p = i * i; p <= n; p += i) {
                    primes[p] = false;
                }
            }
        }
        return primes;
    }

    private static String solve() throws IOException {
        Main obj = new Main();
//        int n = obj.intVal();
//        long[] xx = obj.longArr();
//        long l = xx[0],r = xx[1];
//        int[] a = obj.intArr();
        int[] xx = obj.intArr();
        int  n = xx[0];
        int q = xx[1];
        int[] a = obj.intArr();
        int[] b = new int[n];
        b[0] = 0;
        for(int i=1;i<n;i++){
            if(a[i]==a[i-1]){
                b[i] = b[i-1];
            }
            else b[i] = i;
        }
        StringBuffer ans = new StringBuffer();
        for(int i=0;i<q;i++){
            int[] arr = obj.intArr();
            int l = arr[0]-1,r = arr[1]-1,val = arr[2];
            if(a[r]!=val){
                ans.append((r+1)+"\n");
            }
            else if(a[l]!=val){
                ans.append((l+1)+"\n");
            }else {
                int k = b[r]-1;
                if(k>=l){
                    ans.append((k+1)+"\n");
                }
                else ans.append("-1\n");
            }

        }

        return ans+ "";

    }

    public static void main(String[] args) throws IOException {
        Main ob = new Main();
//        int total_test_case = ob.intVal();
        int total_test_case = 1;
        StringBuffer ans = new StringBuffer();
        String k ;
        for(int test_case =0;test_case<total_test_case;test_case++){
            k = Main.solve();
//            System.out.println(k);
            ans.append(k+"\n");
        }
        System.out.print(ans);
    }
}