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

/**
 *
 * @author umang
 */

public class C622 {
    
    public static int mod = 1000000007;
    
    public static class SegmentTree {
        
        ArrayList<ArrayList<Pair>> list = new ArrayList<>();
 
        SegmentTree(int arr[], int n)  {
            int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
            int max_size = 2 * (int) Math.pow(2, x) - 1;
            for(int i=0;i<=max_size;i++) list.add(new ArrayList<>());
            constructSTUtil(arr, 0, n - 1, 0);
        }
 
        int getMid(int s, int e) {
            return s + (e - s) / 2;
        }

        ArrayList<Pair> getQueryUtil(int ss, int se, int qs, int qe, int si){
            if (qs <= ss && qe >= se)
                return list.get(si);
            if (se < qs || ss > qe)
                return null;
 
            int mid = getMid(ss, se);
            
            ArrayList<Pair> l1 = new ArrayList<>();
            ArrayList<Pair> l2 = new ArrayList<>();
            
            l1 = getQueryUtil(ss, mid, qs, qe, 2 * si + 1);
            l2 = getQueryUtil(mid + 1, se, qs, qe, 2 * si + 2);
            
            if(l1==null){
                l1=l2;
            }
            else if(l2!=null){
                if(l1.get(0).x==l1.get(1).x){
                    if(l1.get(1).i-1>=qs && l1.get(1).i-1<=qe) l1.remove(0);
                    else l1.remove(1);
                    if(l2.get(0).x==l1.get(0).x) l1.add(l2.get(1));
                    else l1.add(l2.get(0));
                }
            }
            
            return l1;
        }
 
        ArrayList<Pair> getQuery(int n, int qs, int qe){
            if (qs < 0 || qe > n - 1 || qs > qe) {
                return null;
            }
            return getQueryUtil(0, n - 1, qs, qe, 0);
        }       
        
 
        ArrayList<Pair> constructSTUtil(int arr[], int ss, int se, int si){
            if (ss == se) {
                list.get(si).add(new Pair(ss+1, arr[ss]));
                list.get(si).add(new Pair(ss+1, arr[ss]));
                return list.get(si);
            }
 
            int mid = getMid(ss, se);
            ArrayList<Pair> l1 = new ArrayList<>();
            ArrayList<Pair> l2 = new ArrayList<>();
            
            l1 = constructSTUtil(arr, ss, mid, si * 2 + 1);
            l2 = constructSTUtil(arr, mid + 1, se, si * 2 + 2);
            
            if(l1.get(0).x==l1.get(1).x){
                list.get(si).add(l1.get(0));
                if(l2.get(0).x==l1.get(0).x) list.get(si).add(l2.get(1));
                else list.get(si).add(l2.get(0));
            }
            else{
                list.get(si).add(l1.get(0));
                list.get(si).add(l1.get(1));
            }
            
            return list.get(si);
        }
    }

    public static void main(String[] args) {
 
        InputReader in = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
                    
        int n = in.nextInt();
        int m = in.nextInt();        
        int[] arr = in.nextIntArray(n);
        
 /*       SegmentTree st = new SegmentTree(arr, n);
        
        while(m>0){
            int l = in.nextInt();
            int r = in.nextInt();
            int x = in.nextInt();
            
            ArrayList<Pair> list = st.getQuery(n, l-1, r-1);
            
            if(list.get(0).x==x && list.get(1).x==x) w.println("-1");
            else if(list.get(0).x==x) w.println(list.get(1).i);
            else if(list.get(1).x==x) w.println(list.get(0).i);
            else if(list.get(0).i>=l && list.get(0).i<=r) w.println(list.get(0).i);
            else w.println(list.get(1).i);
            m--;
        }*/
        int[] dp = new int[n+1];
        dp[n-1]=Integer.MAX_VALUE;
        for(int i=n-2;i>=0;i--){
            if(arr[i]!=arr[i+1]) dp[i]=i+1;
            else dp[i]=dp[i+1];
        }
        
        while(m>0){
            int l = in.nextInt();
            int r = in.nextInt();
            int x = in.nextInt();
            if(arr[l-1]!=x) w.println(l);
            else if(dp[l-1]<=r-1) w.println(dp[l-1]+1);
            else w.println("-1");
            m--;
        }
        
        w.close();
    }
    
    static class Pair{
        int i;
        int x;
        
        public Pair(int i,int x){
            this.i=i;
            this.x=x;
        }
        
    }
    
    static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

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

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

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

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

		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} 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 interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}