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 com.sun.org.apache.xerces.internal.impl.dv.xs.IntegerDV;
import com.sun.org.apache.xerces.internal.impl.xpath.regex.Match;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;


public class Main {
    MyScanner cin = new MyScanner(System.in);
    PrintWriter cout = new PrintWriter(System.out);

    int inf = (int) 2e9;
    int N = (int) 2e5;

    st[] t = new st[N * 5];
    int a[] = new int[N];

    private void run() throws FileNotFoundException {
        //MyScanner cin = new MyScanner(new FileReader("input.txt"));
        //PrintWriter cout = new PrintWriter(new File("output.txt"));
        int n = cin.nextInt(), m = cin.nextInt();
        for (int i = 0; i < n; i++){
            a[i] = cin.nextInt();
        }
        build(1, 0, n - 1);
        while(m > 0){
            m--;
            int l = cin.nextInt() - 1, r = cin.nextInt() - 1, x = cin.nextInt();
            st f = get(1, 0, n - 1, l, r);
            if (f.mx.x == f.mn.x && f.mx.x == x){
                cout.println(-1);
            }
            else{
                if (f.mx.x != x) cout.println(f.mx.pos + 1);
                else cout.println(f.mn.pos + 1);
            }
        }
        cout.close();
    }

    void build(int v, int tl, int tr){
        if (tl == tr) t[v] = new st(new val(a[tl], tl), new val(a[tl], tl));
        else{
            int tm = (tl + tr) >> 1;
            build(v * 2, tl, tm);
            build(v * 2 + 1, tm + 1, tr);
            t[v] = merge(t[v * 2], t[v * 2 + 1]);
        }
    }

    st get(int v, int tl, int tr, int l, int r){
        if (l > r) return new st(new val(-inf, -inf), new val(inf, inf));
        if (tl == l && r == tr) return t[v];
        int tm = (tl + tr) >> 1;
        return merge(get(v * 2, tl, tm, l, Math.min(r, tm)), get(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r));
    }

    class val{
        int x, pos;
        val(int a1, int b1){
            x = a1;
            pos = b1;
        }
    }

    class st{
        val mx, mn;
        st(val a1, val b1){
            mx = a1;
            mn = b1;
        }
    }

    st merge(st q, st w){
        st res = new st(new val(0, 0), new val(0, 0));
        if (q.mx.x > w.mx.x) res.mx = q.mx;
        else res.mx = w.mx;
        if (q.mn.x < w.mn.x) res.mn = q.mn;
        else res.mn = w.mn;
        return res;
    }

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

    class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner(FileReader in){
            br = new BufferedReader(in);
        }
        public MyScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
        }

        String next(){
            while(st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        String tmp = "";
        int nextInt(){return Integer.parseInt(next());}
        double nextDouble(){return Double.parseDouble(next());}
        long nextLong(){return Long.parseLong(next());}

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}