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.Scanner;

public class Problem_0622C {

    static int readInt(BufferedReader rd) throws Exception {
        return Integer.valueOf(rd.readLine());
    }

    static int[] readIntArray(BufferedReader rd) throws Exception {
        String[] values = rd.readLine().split(" ");
        int[] res = new int[values.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = Integer.valueOf(values[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        try{
            BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
            int[] arr = readIntArray(input);
            int n = arr[0];
            int m = arr[1];
            int[] a = readIntArray(input);
            int[] range1k = new int[n];
            range1k[0] = 0;
            for (int i = 1; i < n; i++) {
                if (a[i] == a[i - 1]) {
                    range1k[i] = range1k[i-1];
                } else {
                    range1k[i] = i;
                }
            }

            BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
            //StringBuilder sb = new StringBuilder(10*m);
            for (int i = 0; i < m; i++) {
                int[] line = readIntArray(input);

                int l = line[0] - 1;
                int r = line[1] - 1;
                int x = line[2];

                int c = range1k[r];

                if (c < l) c = l;

                //sb.append(l < c ? (a[l] != x ? l + 1 : (a[c] != x ? c + 1 : c)) : (a[l] != x ? l + 1 : -1));
                //sb.append("\n");
                output.write(new Integer(l < c ? (a[l] != x ? l + 1 : (a[c] != x ? c + 1 : c)) : (a[l] != x ? l + 1 :
                        -1)).toString() + "\n");
            }

            //output.write(sb.toString());
            output.flush();
            output.close();
        } catch (Exception ex){

        }

    }
}