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.*;
import java.lang.Math;
import java.math.BigInteger;

public class Problem {

	public static void main(String[] args) throws IOException {

		new Problem().run();
	}

	BufferedReader in;
	PrintWriter out;
	StringTokenizer tok;
	static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
	Problem() throws FileNotFoundException{

		if (ONLINE_JUDGE) {
			in = new BufferedReader(new InputStreamReader(System.in)); 
            out = new PrintWriter(System.out); 
		} else {
			in = new BufferedReader(new FileReader("input.txt"));
			out = new PrintWriter("output.txt");
		}
		tok = new StringTokenizer("");
	}

	// ======================================================

	int INF = Integer.MAX_VALUE;
	List<Integer>[] graph;
	boolean[] used;
	long[] time;
	int[] def;
	int[] ans;
	ArrayList<Integer> ansPath = new ArrayList<>();
	boolean flag = false;
	int maxLength;
	int curClone = 0;
	void solve() throws IOException {
		int n = rI();
		int m = rI();
		int[] a = rA(n);
		int[] nearDiffInd = new int[n];
		int j=0;
		int cur = a[0];
		while(j<n&&a[j]==a[0]){
			nearDiffInd[j]=-1;
			++j;
		}
		int lastDiff = j-1;
		for(int i=j;i<n;++i){
			nearDiffInd[i] = lastDiff;
			cur=a[i];
			i++;
			while(i<n&&a[i]==cur){
				nearDiffInd[i] = lastDiff;
				i++;
			}
			if(i>=n){
				break;
			}
			i--;
			lastDiff = i;
			
		}
		/*
		for(int i: nearDiffInd){
			out.print(i+" ");
		}*/
		out.println();
		for(int i=0;i<m;++i){
			int l = rI();
			int r = rI();
			int x = rI();
			if(a[r-1]!=x){
				out.println(r);
			}else{
				if(nearDiffInd[r-1]>=l-1){
					out.println(nearDiffInd[r-1]+1);
				}else{
					out.println(-1);
				}
			}
		}
	}
	
	// ======================================================
	void run() throws IOException {
		solve();
		out.close();
	}


	int sqrt(double m){
		int l = 0;
		int r = 1000000000+9;
		int i=1000;
		while(r-l>1){
			int mid = (r+l)/2;
			if(mid*mid>m){
				r = mid;
			}else{
				l = mid;
			}
		}
		return l;
	}
	int countPow(int m,int n){
		int ans = 0;
		while(m%n==0&&m>0){
			ans++;
			m/=n;
		}
		return ans;
	}
	long binPow(long a, long b){
		if(b == 0){
			return 1;
		}
		if(b%2==1){
			return a*binPow(a,b-1);
		}else{
			long c = binPow(a,b/2);
			return c*c;
		}
		
	}
	long gcd(long a, long b){
		return b==0?a:gcd(b,a%b);
	}
	
	long pow(long x, long k){
		long ans=1;
		for(int i=0;i<k;++i){
			ans*=x;
		}
		return ans;
	}
	//////////////////////////////////////////////////////////////////////


	String delimiter = " ";
	String readLine() throws IOException {
		return in.readLine();
	}
	String rS() throws IOException {
		while (!tok.hasMoreTokens()) {
			String nextLine = readLine();
			if (null == nextLine)
				return null;

			tok = new StringTokenizer(nextLine);
		}

		return tok.nextToken(delimiter);
	}
	int rI() throws IOException {
		return Integer.parseInt(rS());
	}

	long rL() throws IOException {
		return Long.parseLong(rS());
	}
	int[] rA(int b) {
		int a[] = new int[b];
		for (int i = 0; i < b; i++) {
			try {
				a[i] = rI();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return a;
	}
	
	int[] readSortedIntArray(int size) throws IOException {
	        Integer[] array = new Integer[size];

	        for (int index = 0; index < size; ++index) {
	            array[index] = rI();
	        }
	        Arrays.sort(array);

	        int[] sortedArray = new int[size];
	        for (int index = 0; index < size; ++index) {
	            sortedArray[index] = array[index];
	        }

	        return sortedArray;
	    }

}