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

public class CF622C{
    static class Element implements Comparable<Element>{
        int val, idx;

        public Element(int val, int idx){
            this.val = val;
            this.idx = idx;
        }

        @Override
        public int compareTo(Element o){
            return val-o.val;
        }
    }

    public static void main(String[] args){
        InputReader scn = new InputReader(System.in);
        OutputWriter out = new OutputWriter(System.out);
        int n = scn.readInt();
        int m = scn.readInt();
        int[] all = new int[n];
        Element[] allE = new Element[n];
        for (int i=0; i<n; i++){
            all[i] = scn.readInt();
            allE[i] = new Element(all[i], i+1);
        }
        RMQ<Element> rmq = new RMQ<>(allE);
        for (int i=0; i<m; i++){
            int l = scn.readInt()-1;
            int r = scn.readInt()-1;
            int x = scn.readInt();
            Element maxe = (Element)rmq.getMax(l, r);
            Element mine = (Element)rmq.getMin(l, r);
            if (maxe.val != x){
                out.printLine(maxe.idx);
            } else if (mine.val != x) {
                out.printLine(mine.idx);
            } else {
                out.printLine(-1);
            }
        }
        out.close();
    }
}

class RMQ<E extends Comparable<E>>{
    private int[][] maxq, minq;
    private E[] allE;
    final private static double EPS = 1e-8;
    private static int[] logNall;

    static {
        logNall = new int[200002];
        int now = 0;
        for (int i=1; i<200002; i++){
            if (i>=(1<<(now+1))) now++;
            logNall[i] = now;
        }
    }

    public RMQ(E[] allE){
        int n = allE.length;
        int logN = (int) (Math.log(1.0*n)/Math.log(2.0)+EPS);
        this.allE = allE;
        maxq = new int[n][logN+1];
        minq = new int[n][logN+1];
        for (int i=0; i<n; i++){
            maxq[i][0] = i;
            minq[i][0] = i;
        }
        for (int j=1; j<=logN; j++){
            for (int i=n-1; i>=0; i--){
                if (this.getUpper(i, j-1)+1>=n){
                    maxq[i][j] = maxq[i][j-1];
                    minq[i][j] = minq[i][j-1];
                }
                else {
                    maxq[i][j] = this.maxIdx(maxq[i][j-1], maxq[this.getUpper(i, j-1)+1][j-1]);
                    minq[i][j] = this.minIdx(minq[i][j-1], minq[this.getUpper(i, j-1)+1][j-1]);
                }
            }
        }
    }

    public E getMax(int l, int r){
        int logN = logNall[r-l+1];
        return allE[this.maxIdx(maxq[l][logN], maxq[this.getLower(r, logN)][logN])];
    }

    public E getMin(int l, int r){
        int logN = logNall[r-l+1];
        return allE[this.minIdx(minq[l][logN], minq[this.getLower(r, logN)][logN])];
    }

    private int getUpper(int i, int j){
        return i+(1<<j)-1;
    }

    private int getLower(int i, int j){
        return i-(1<<j)+1;
    }

    private int maxIdx(int idx1, int idx2){
        return allE[idx1].compareTo(allE[idx2]) > 0 ? idx1 : idx2;
    }

    private int minIdx(int idx1, int idx2){
        return allE[idx1].compareTo(allE[idx2]) < 0 ? idx1 : idx2;
    }
}

class InputReader {

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String readString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public String next() {
        return readString();
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

    public void flush() {
        writer.flush();
    }

}

class IOUtils {

    public static int[] readIntArray(InputReader in, int size) {
        int[] array = new int[size];
        for (int i = 0; i < size; i++)
            array[i] = in.readInt();
        return array;
    }

}