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.util.*;
import java.io.*;

public class ForProblems {

    Random rnd = new Random();

    void solve() throws IOException {

        int n = readInt();
        int m = readInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = readInt();

        int[] l = new int[m];
        int[] r = new int[m];
        int[] x = new int[m];
        for (int i = 0; i < m; ++i) {
            l[i] = readInt() - 1;
            r[i] = readInt() - 1;
            x[i] = readInt();
        }

        int[] ans = new int[n];
        ans[0] = -2;
        for (int i = 1; i < n; ++i) {

            if (a[i - 1] != a[i]) {
                ans[i] = i - 1;
            } else {
                ans[i] = ans[i - 1];
            }
        }

        for (int i = 0; i < m; ++i) {

            if (a[r[i]] != x[i]) {
                out.println(r[i] + 1);
            } else {
                if (ans[r[i]] < l[i])
                    out.println("-1");
                else
                    out.println(ans[r[i]] + 1);
            }
        }
    }

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args){
        new ForProblems().run();
    }

    public void run() {
        try {
            long timeBegin = System.currentTimeMillis();
            Locale.setDefault(Locale.US);

            init();
            solve();

            out.close();

            long timeEnd = System.currentTimeMillis();
            System.err.println("Time = " + (timeEnd - timeBegin));
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while(!tok.hasMoreTokens()){
            try{
                tok = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    void init() throws FileNotFoundException {
        Locale.setDefault(Locale.US);

        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }
}