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.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

 public class Test
 {
    
    static PrintWriter pw = new PrintWriter(System.out);
    static class SegmentTree
    {
        int[] a;
        int[] seg;
        int n;
        int type;
        SegmentTree(int[] ar , int t)
        {
            a = ar;
            n = a.length;
            seg = new int[4 * n];
            type = t;
            build(1,0,n-1 );
        }
        
        public int get(int i , int j)
        {
            i--;
            j--;
            return this.get(1, 0, n-1, i, j); 
        }
        
        private void build(int p , int L , int R )
        {
            if(L == R)
            {
                seg[p] = L;
                return;
            }
            
            int left = p<<1;
            int right = (p<<1) + 1;
            int mid = (L+R)/2;
            build(left , L , mid );
            build(right , mid + 1 , R );
            
            int p1 = seg[left];
            int p2 = seg[right];
            
            if(type == 0)
            {//min
                if(a[p1] < a[p2])
                    seg[p] = p1;
                else
                    seg[p] = p2;
            }
            else
            {
                if(a[p1] > a[p2])
                    seg[p] = p1;
                else
                    seg[p] = p2;
            }
                
            
        }
        
        private int get(int p , int L , int R , int i , int j)
        {
            if(L >= i && R <= j)
                return seg[p];
            if(i > R || j < L)
                return -1;
            
            int left = p<<1;
            int right = (p<<1) + 1;
            int mid = (L+R)/2;
            
            int p1 = get(left , L ,mid , i , j);
            int p2 = get(right, mid + 1 , R , i , j);
            
            if(p1 == -1)
                return p2;
            if(p2 == -1)
                return p1;
            
            if(type == 0)
            {//min
                if(a[p1] < a[p2])
                    return p1;
                else
                    return p2;
            }
            else
            {
                if(a[p1] > a[p2])
                    return p1;
                else
                    return p2;
            }
        }
    }
    
 
    public static void main(String[] args)throws Exception
    {
        Reader.init(System.in);
        int n = Reader.nextInt();
        int m = Reader.nextInt();
        StringBuilder res = new StringBuilder();
        int[] ar = new int[n];
        for(int i = 0 ; i<n ; i++)
                ar[i] = Reader.nextInt();
        
        SegmentTree segMin = new SegmentTree(ar , 0);
        SegmentTree segMax = new SegmentTree(ar , 1);

        for(int i = 0 ; i<m ; i++)
        {
            int a = Reader.nextInt();
            int b = Reader.nextInt();
            int x = Reader.nextInt();
            int min = segMin.get(a, b);
            int max = segMax.get(a, b);
            if(x == ar[min] && x == ar[max])
                res.append("-1\n");
            else if(x == ar[min])
                res.append(max+1).append("\n");
            else
                res.append(min+1).append("\n");
            
        }
        
  
        pw.print(res);
        pw.close();
    }
}


class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    public static int pars(String x) {
        int num = 0;
        int i = 0;
        if (x.charAt(0) == '-') {
            i = 1;
        }
        for (; i < x.length(); i++) {
            num = num * 10 + (x.charAt(i) - '0');
        }

        if (x.charAt(0) == '-') {
            return -num;
        }

        return num;
    }

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static void init(FileReader input) {
        reader = new BufferedReader(input);
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return pars(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}