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.util.*;
import java.io.*;
import java.text.DecimalFormat;

public class CodeForces {

    static int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
    static int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        PrintWriter writer = new PrintWriter(System.out);
    
        int n = Reader.nextInt(), m = Reader.nextInt();
        ArrayList<Interval> arr[] = new ArrayList[1000001];
        
        for (int i = 1; i <= n; i++) {
            int x = Reader.nextInt();
            
            if(arr[x] == null)
                arr[x] = new ArrayList<>();
            
            if(arr[x].isEmpty() || arr[x].get(arr[x].size()-1).right+1 != i)
                arr[x].add(new Interval(i,i));
            else
                arr[x].get(arr[x].size()-1).right++;
        }
        
        /*
        for (int i = 1; i <= 5; i++) {
            if(arr[i] == null)
                continue;
            
            System.out.print(i + "  ");
            for (int j = 0; j < arr[i].size(); j++) {
                System.out.print(arr[i].get(j).left + "," + arr[i].get(j).right + "  ");
            }
            
            System.out.println("");
        }*/
        
        for (int i = 0; i < m; i++) {
            int l = Reader.nextInt(), r = Reader.nextInt(), x = Reader.nextInt();
            
            if(arr[x] == null)
                writer.println(l);
            
            else {
                int first = 0, last = arr[x].size()-1;
                Interval temp = null;
                int indx = -1;
                while(first <= last){
                    int mid = (first+last)/2;
                    
                    if(arr[x].get(mid).left > l)
                        last = mid-1;
                    else {
                        first = mid+1;
                        indx = mid;
                    }
                }
                
                if(indx == -1){
                    writer.println(l);
                    continue;
                }
                    
                temp = arr[x].get(indx);
                    
                if(temp.right < l)
                    writer.println(l);
                else if(temp.right+1 <= r)
                    writer.println(temp.right+1);
                else
                    writer.println(-1);
            }
        }
        writer.flush();
    }
}

class Interval{
    int left, right;

    public Interval(int left, int right) {
        this.left = left;
        this.right = right;
    }
    
}
class Edge implements Comparable<Edge> {

    int to;
    int from;
    int cost;

    Edge(int a, int b, int c) {
        from = a;
        to = b;
        cost = c;
    }

    @Override
    public int compareTo(Edge t) {
        return cost - t.cost;
    }
}

class Pair implements Comparable<Pair> {

    int x;
    int y;

    Pair(int a, int b) {
        x = a;
        y = b;
    }

    @Override
    public boolean equals(Object o) {
        return x == ((Pair) o).x && y == ((Pair) o).y;
    }

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public int compareTo(Pair t) {
        if (x <= t.x && y <= t.y) {
            return 1;
        }
        return -1;
    }

}

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());
    }
}