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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Not_eq solver = new Not_eq();
        solver.solve(1, in, out);
        out.close();
    }

    static class Not_eq {
        long[] tree;
        long[] index;
        long[] tree2;
        long[] index2;
        long[] arr;

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int m = in.scanInt();
            arr = new long[n];
            for (int i = 0; i < n; i++) arr[i] = in.scanInt();
            tree = new long[(4 * (n + 5)) + 5];
            tree2 = new long[(4 * (n + 5)) + 5];
            index = new long[(4 * (n + 5)) + 5];
            index2 = new long[(4 * (n + 5)) + 5];
            build(1, 0, n - 1);
            build2(1, 0, n - 1);
            while (m-- > 0) {
                int l = in.scanInt() - 1;
                int r = in.scanInt() - 1;
                int x = in.scanInt();
                int index1 = (int) query(1, 0, n - 1, l, r);
                int index2 = (int) query2(1, 0, n - 1, l, r);
                if (arr[index1] != x) out.println(index1 + 1);
                else if (arr[index2] != x) out.println(index2 + 1);
                else out.println(-1);
            }

        }

        void build(int node, int start, int end) {
            if (start == end) {
                tree[node] = arr[start];
                index[node] = start;
            } else {
                int mid = (start + end) / 2;
                build(2 * node, start, mid);
                build((2 * node) + 1, mid + 1, end);
                tree[node] = Math.max(tree[2 * node], tree[(2 * node) + 1]);
                if (tree[2 * node] > tree[(2 * node) + 1]) {
                    index[node] = index[2 * node];
                } else {
                    index[node] = index[(2 * node) + 1];
                }
            }
        }

        long query(int node, int start, int end, int l, int r) {
            if (r < start || end < l) {
                return -1;
            }
            if (l <= start && end <= r) {
                return index[node];
            }
            int mid = (start + end) / 2;
            long p1 = query((2 * node), start, mid, l, r);
            long p2 = query((2 * node) + 1, mid + 1, end, l, r);
            if (p1 == -1) return p2;
            if (p2 == -1) return p1;
            if (arr[(int) p1] > arr[(int) p2]) return p1;
            else return p2;
        }

        void build2(int node, int start, int end) {
            if (start == end) {
                tree2[node] = arr[start];
                index2[node] = start;
            } else {
                int mid = (start + end) / 2;
                build2(2 * node, start, mid);
                build2((2 * node) + 1, mid + 1, end);
                tree2[node] = Math.min(tree2[2 * node], tree2[(2 * node) + 1]);
                if (tree2[2 * node] < tree2[(2 * node) + 1]) {
                    index2[node] = index2[2 * node];
                } else {
                    index2[node] = index2[(2 * node) + 1];
                }
            }
        }

        long query2(int node, int start, int end, int l, int r) {
            if (r < start || end < l) {
                return -1;
            }
            if (l <= start && end <= r) {
                return index2[node];
            }
            int mid = (start + end) / 2;
            long p1 = query2((2 * node), start, mid, l, r);
            long p2 = query2((2 * node) + 1, mid + 1, end, l, r);
            if (p1 == -1) return p2;
            if (p2 == -1) return p1;
            if (arr[(int) p1] < arr[(int) p2]) return p1;
            else return p2;
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}