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:
//package main;

import java.io.*;
import java.util.*;

public final class Main {
    BufferedReader br;
    StringTokenizer stk;
    
    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    {
        stk = null;
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    long mod = 998244353;
    StringBuilder res = new StringBuilder(1000005);
    void run() throws Exception {
        int n = ni();
        int q = ni();
        
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = ni();
        }
        
        SegmentTreeMin min = new SegmentTreeMin(a);
        SegmentTreeMax max = new SegmentTreeMax(a);
        
        while(q-- > 0) {
            int L = ni() - 1;
            int R = ni() - 1;
            int V = ni();
            
            int[] mn = min.query(L, R);
            int[] mx = max.query(L, R);
            
            if(mn[1] == mx[1] && mn[1] == V) {
                res.append("-1\n");
            } else {
                if(mn[1] != V) {
                    res.append(mn[0]).append("\n");
                } else {
                    res.append(mx[0]).append("\n");
                }
            }
        }
        
        System.out.print(res);
    }
    
    class SegmentTreeMin {
        int L, M;
        Node[] tree;
        int fakeIdx = -1;
        //change spot
        int filler = Integer.MAX_VALUE / 2;
        
        public SegmentTreeMin(int[] a) {
            L = a.length;
            if(Integer.bitCount(L) == 1) {
                L <<= 1;
            } else {
                L = Integer.highestOneBit(L) << 2;
            }
            M = L >> 1;
            tree = new Node[L];
            
            for(int i = M, j = 0; j < a.length; i++, j++) {
                tree[i] = new Node(j + 1, a[j]); // one based
            }
            for(int i = L - 1; i >= 0; i--) {
                if(tree[i] != null) {
                    break;
                }
                tree[i] = new Node(fakeIdx, filler);
            }
            for(int i = M - 1; i > 0; i--) {
                Node fc = tree[2 * i];
                Node sc = tree[2 * i + 1];
                //change spot
                if(fc.value < sc.value) {
                    tree[i] = new Node(fc.idx, fc.value);
                } else {
                    tree[i] = new Node(sc.idx, sc.value);
                }
            }
        }
        
        int[] query(int L, int R) {
            return query(1, L, R, 0, M - 1).toIntArray();
        }
        
        Node query(int idx, int ql, int qr, int cl, int cr) {
            if(cl >= ql && cr <= qr) {
                return tree[idx];
            } else if(cl > qr || cr < ql) {
                return new Node(fakeIdx, filler);
            } else {
                int mid = (cl + cr) / 2;
                Node left  = query(2 * idx, ql, qr, cl, mid);
                Node right = query(2 * idx + 1, ql, qr, mid + 1, cr);
                //change spot
                return left.value < right.value ? left : right;
            }
        }
        
        class Node {
            int idx, value;
            public Node(int idx, int value) {
                this.idx = idx;
                this.value = value;
            }
            int[] toIntArray() {
                return new int[] {idx, value};
            }
        }
    }
    
    class SegmentTreeMax {
        int L, M;
        Node[] tree;
        int fakeIdx = -1;
        //change spot
        int filler = Integer.MIN_VALUE / 2;
        
        public SegmentTreeMax(int[] a) {
            L = a.length;
            if(Integer.bitCount(L) == 1) {
                L <<= 1;
            } else {
                L = Integer.highestOneBit(L) << 2;
            }
            M = L >> 1;
            tree = new Node[L];
            
            for(int i = M, j = 0; j < a.length; i++, j++) {
                tree[i] = new Node(j + 1, a[j]); // one based
            }
            for(int i = L - 1; i >= 0; i--) {
                if(tree[i] != null) {
                    break;
                }
                tree[i] = new Node(fakeIdx, filler);
            }
            for(int i = M - 1; i > 0; i--) {
                Node fc = tree[2 * i];
                Node sc = tree[2 * i + 1];
                //change spot
                if(fc.value > sc.value) {
                    tree[i] = new Node(fc.idx, fc.value);
                } else {
                    tree[i] = new Node(sc.idx, sc.value);
                }
            }
        }
        
        int[] query(int L, int R) {
            return query(1, L, R, 0, M - 1).toIntArray();
        }
        
        Node query(int idx, int ql, int qr, int cl, int cr) {
            if(cl >= ql && cr <= qr) {
                return tree[idx];
            } else if(cl > qr || cr < ql) {
                return new Node(fakeIdx, filler);
            } else {
                int mid = (cl + cr) / 2;
                Node left  = query(2 * idx, ql, qr, cl, mid);
                Node right = query(2 * idx + 1, ql, qr, mid + 1, cr);
                //change spot
                return left.value > right.value ? left : right;
            }
        }
        
        class Node {
            int idx, value;
            public Node(int idx, int value) {
                this.idx = idx;
                this.value = value;
            }
            int[] toIntArray() {
                return new int[] {idx, value};
            }
        }
    }
    
    //Reader & Writer
    String nextToken() throws Exception {
        if (stk == null || !stk.hasMoreTokens())
            stk = new StringTokenizer(br.readLine(), " ");
        return stk.nextToken();
    }

    char[] nc() throws Exception {
        return nextToken().toCharArray();
    }

    int ni() throws Exception {
        return Integer.parseInt(nextToken());
    }

    long nl() throws Exception {
        return Long.parseLong(nextToken());
    }
    
    double nd() throws Exception {
        return Double.parseDouble(nextToken());
    }
    
    //Some Misc methods
    int get(int l, int r, int[] a) {
        return l == 0 ? a[r] : a[r] - a[l - 1];
    }
    
    void shuffle(long[] a) {
        Random r = new Random();
        for(int i = 0; i < a.length; i++) {
            int idx = r.nextInt(a.length);
            long temp = a[i];
            a[i] = a[idx];
            a[idx] = temp;
        }
    }
    
    void reverse(long[] a) {
        for(int i = 0, j = a.length - 1; i < j; i++, j--) {
            long temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
}