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

import static java.lang.Integer.parseInt;

public class C_Not_Equal_on_a_Segment {
    static class pair {
        int max, min;

        public pair(int max, int min) {
            this.max = max;
            this.min = min;
        }
    }

    static int n, m, l, r, x, ar[];
    static pair seg[];

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer tk = new StringTokenizer(in.readLine());
        n = parseInt(tk.nextToken());
        m = parseInt(tk.nextToken());
        seg = new pair[6 * 100000];
        ar = new int[n + 1];
        ar[0] = -1;
        tk = new StringTokenizer(in.readLine());
        for (int i = 1; i <= n; i++) {
            ar[i] = parseInt(tk.nextToken());
        }
        build(1,1,n);
        for (int i = 0; i < m; i++) {
            tk = new StringTokenizer(in.readLine());
            l = parseInt(tk.nextToken());
            r = parseInt(tk.nextToken());
            x = parseInt(tk.nextToken());
            pair ans = get(1,1,n);
            if(ar[ans.min] == ar[ans.max]){
                if(x != ar[ans.min]){
                    out.write(ans.min+"\n");
                }
                else
                    out.write(-1+"\n");
            }
            else {
                if(ar[ans.min] != x)
                    out.write(ans.min+"\n");
                else if(ar[ans.max] != x)
                    out.write(ans.max+"\n");
                else
                    out.write(-1+"\n");
            }
        }
        out.flush();
    }

    static void build(int n,int s,int e){
        if(s == e){
            seg[n] = new pair(s,s);
            return;
        }
        build(2*n,s,(s+e)/2);
        build(2*n+1,(s+e)/2+1,e);
        seg[n] = new pair(0,0);
        if(ar[seg[2 * n].min] <= ar[seg[2 * n + 1].min] ) {
            seg[n].min = seg[2 * n].min;
        }
        else {
            seg[n].min = seg[2 * n + 1].min;
        }
        if(ar[seg[2*n].max] >= ar[seg[2*n+1].max]) {
            seg[n].max = seg[2 * n].max;
        }
        else {
            seg[n].max = seg[2 * n + 1].max;
        }
    }

    static pair get(int n,int s,int e){
        if(s > r || e < l){
            return new pair(-1,-1);
        }
        if(s >= l && e <= r){
            return seg[n];
        }
        pair p1 = get(2*n,s,(s+e)/2);
        pair p2 = get(2*n+1,(s+e)/2+1,e);
        pair ans = new pair(0,0);
        if(p1.min == -1 && p1.max == -1) {
            return p2;
        }
        if(p2.min == -1 && p2.max == -1) {
            return p1;
        }
        if(ar[p1.min] <= ar[p2.min])
            ans.min = p1.min;
        else
            ans.min = p2.min;
        if(ar[p1.max] >= ar[p2.max])
            ans.max = p1.max;
        else
            ans.max = p2.max;
        return ans;
    }
}