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.InputStreamReader;
import java.io.OutputStreamWriter;

public class Segment {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] A = iarray(in.readLine(), 2);
        int n = A[0];
        int m = A[1];
        int[] a = iarray(in.readLine(), n);
        int[] p = new int[n];
        p[0] = -1;
        for (int i=1; i<n; i++) {
            if (a[i]==a[i-1]) {
                p[i] = p[i-1];
            }
            else {
                p[i] = i-1;
            }
        }
        int[] l = new int[m];
        int[] r = new int[m];
        int[] x = new int[m];
        for (int i=0; i<m; i++) {
            int[] B = iarray(in.readLine(), 3);
            int pos = 0;
            l[i] = B[0];
            r[i] = B[1];
            x[i] = B[2];
            if (x[i]==a[r[i]-1]) {
                pos = p[r[i]-1];
                if (pos<(l[i]-1)) {
                    pos = -1;
                }
            }
            else {
                pos = r[i]-1;
            }
            if (pos!=-1) {
                out.write(pos+1+"\n");
            }
            else {
                out.write("-1\n");
            }
        }
        out.flush();
    }
    
    private static int iparse (String s) {
        int n = Integer.parseInt(s);
        return n;
    }
    
    private static long lparse (String s) {
        long n = Long.parseLong(s);
        return n;
    }
    
    private static double dparse (String s) {
        double n = Double.parseDouble(s);
        return n;
    }
    
    private static int[] iarray (String s, int n) {
        String[] s1 = s.split(" ");
        int[] A = new int[n];
        for (int i=0; i<n; i++) {
            A[i] = Integer.parseInt(s1[i]);
        }
        return A;
    }
    
    private static long[] larray (String s, int n) {
        String[] s1 = s.split(" ");
        long[] A = new long[n];
        for (int i=0; i<n; i++) {
            A[i] = Long.parseLong(s1[i]);
        }
        return A;
    }
    
    private static double[] darray (String s, int n) {
        String[] s1 = s.split(" ");
        double[] A = new double[n];
        for (int i=0; i<n; i++) {
            A[i] = Double.parseDouble(s1[i]);
        }
        return A;
    }
}