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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.*;

public class C622 {
    public static void main(String[] args) throws IOException {
        ContestsScanner sc = new ContestsScanner();
        int n = sc.nextInt();
        int q = sc.nextInt();
        int[] vals = sc.nextInts(n);
        int[] prevDiff = genNextDiff(vals);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int x = sc.nextInt();
            l--;
            r--;
            if (vals[r] != x) {
                out.print((r + 1)+"\n");
            } else {
                if (prevDiff[r] >= l) {
                    out.print((prevDiff[r] + 1)+"\n");
                } else {
                    out.print("-1\n");
                }
            }
        }
        out.close();
    }

    private static int[] genNextDiff(int[] vals) {
        int[] res = new int[vals.length];
        Arrays.fill(res, -1);
        for (int i = 1; i < vals.length; i++) {
            if (vals[i] != vals[i - 1]) {
                res[i] = i - 1;
            } else {
                res[i] = res[i - 1];
            }
        }
        return res;
    }

    public static class ContestsScanner {

        private final BufferedReader br;
        private StringTokenizer tokenizer;

        public ContestsScanner() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = new StringTokenizer(br.readLine());
        }

        String nextToken() {
            if (!tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.valueOf(nextToken());
        }

        int[] nextInts(int n) {
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = Integer.valueOf(nextToken());
            }
            return result;
        }

        long nextLong() {
            return Long.valueOf(nextToken());
        }
    }
}