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.io.PrintWriter;

public class Main {

    public static final int MAXIMUM_VALUE = (int)1e6;

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        InputReader inputReader = new InputReader(in);
        PrintWriter out = new PrintWriter(System.out);

        int[][] positions = new int[MAXIMUM_VALUE + 10][];
        int[] count = new int[MAXIMUM_VALUE+10];
        int[] values = new int[200010];

        int n = inputReader.getNextInt();
        int m = inputReader.getNextInt();
        for(int i = 1; i <= n; i++) {
            values[i] = inputReader.getNextInt();
            count[values[i]]++;
        }
        for(int i = 1; i <= MAXIMUM_VALUE; i++) {
            positions[i] = new int[count[i]];
            count[i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            positions[values[i]][count[values[i]]++] = i;
        }

        for(int i = 0; i < m; i++) {
            int l = inputReader.getNextInt();
            int r = inputReader.getNextInt();
            int x = inputReader.getNextInt();

            out.println(getAnswer(l, r, positions[x]));
        }

        in.close();
        out.close();
    }

    public static int getAnswer(int l, int r, int[] pos) {
        int posl = binarySearch(pos, l, 0, pos.length - 1);
        int posr = binarySearch(pos, r, 0, pos.length - 1);
        if(posl == -1) {
            return l;
        }
        if(posr == -1) {
            return r;
        }
        if(posr - posl == l-r) {
            return -1;
        }
        while(l <= r) {
            int mid = (l+r) / 2;
            int posmid = binarySearch(pos, mid, posl, posr);
            if(posmid == -1) {
                return mid;
            }
            if(mid - l == posmid - posl) {
                l = mid + 1;
                posl = posmid + 1;
            } else {
                r = mid - 1;
                posr = posmid - 1;
            }
        }
        return -1;
    }

    public static int binarySearch(int[] pos, int val, int l, int r) {
        int ans = -1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(pos[mid] == val) {
                ans = mid;
            }
            if(pos[mid] <= val) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    public static class InputReader {

        static final String SEPARATOR = " ";

        String[] split;
        int head = 0;
        BufferedReader in;

        public InputReader(BufferedReader in) {
            this.in = in;
        }

        private void fillBuffer() throws IOException {
            if(split == null || head >= split.length) {
                head = 0;
                split = in.readLine().split(SEPARATOR);
            }
        }

        public String getNextToken() throws IOException {
            fillBuffer();
            return split[head++];

        }

        public int getNextInt() throws IOException {
            return Integer.parseInt(getNextToken());
        }

        public long getNextLong() throws IOException {
            return Long.parseLong(getNextToken());
        }
    }

}