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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class C {
	int N,Q,K;
	int[] A;
	int[] minArray,minIndex,maxArray,maxIndex;
	int M,L;

	public void init(){
		L = 1;
		while(L < N){
			L <<= 1;
		}
		M = L - 1;
		L <<= 1;

		minArray = new int[L];
		minIndex = new int[L];
		maxArray = new int[L];
		maxIndex = new int[L];

		Arrays.fill(minArray,Integer.MAX_VALUE);
		Arrays.fill(maxArray,Integer.MIN_VALUE);

		for(int i = 0;i < N;i++){

			minArray[M + i] = A[i];
			maxArray[M + i] = A[i];

			minIndex[M + i] = i;
			maxIndex[M + i] = i;
		}

		for(int i = M - 1;i >= 0;i--){

			int[] mergedMax = maxMerge(maxArray[i * 2 + 1],maxIndex[i * 2 + 1],maxArray[i * 2 + 2],maxIndex[i * 2 + 2]);
			int[] mergedMin = minMerge(minArray[i * 2 + 1],minIndex[i * 2 + 1],minArray[i * 2 + 2],minIndex[i * 2 + 2]);

			maxArray[i] = mergedMax[0];
			maxIndex[i] = mergedMax[1];

			minArray[i] = mergedMin[0];
			minIndex[i] = mergedMin[1];
		}
	}

	public int[] minMerge(int leftMin,int leftIndex,int rightMin,int rightIndex){
		int[] ret = new int[2];

		if(leftMin <= rightMin){
			ret[0] = leftMin;
			ret[1] = leftIndex;
		}else{
			ret[0] = rightMin;
			ret[1] = rightIndex;
		}
		return ret;
	}

	public int[] maxMerge(int leftMax,int leftIndex,int rightMax,int rightIndex){
		int[] ret = new int[2];

		if(leftMax >= rightMax){
			ret[0] = leftMax;
			ret[1] = leftIndex;
		}else{
			ret[0] = rightMax;
			ret[1] = rightIndex;
		}
		return ret;
	}

	public int[] maxQuery(int l,int r,int index,int b,int e){
		if(e <= l || r <= b){
			return new int[]{Integer.MIN_VALUE,0};
		}

		if(l <= b && e <= r){
			return new int[]{maxArray[index],maxIndex[index]};
		}

		int[] left = maxQuery(l,r,index * 2 + 1,b,(b + e) / 2);
		int[] right = maxQuery(l,r,index * 2 + 2,(b + e)/ 2,e);

		return maxMerge(left[0],left[1],right[0],right[1]);
	}

	public int[] minQuery(int l,int r,int index,int b,int e){
		if(e <= l || r <= b){
			return new int[]{Integer.MAX_VALUE,0};
		}

		if(l <= b && e <= r){
			return new int[]{minArray[index],minIndex[index]};
		}

		int[] left = minQuery(l,r,index * 2 + 1,b,(b + e) / 2);
		int[] right = minQuery(l,r,index * 2 + 2,(b + e)/ 2,e);

		return minMerge(left[0],left[1],right[0],right[1]);
	}

	public void solve() {
		N = nextInt();
		Q = nextInt();
		A = new int[N];
		for(int i = 0;i < N;i++){
			A[i] = nextInt();
		}

		init();
		for(int i = 0;i < Q;i++){
			int l = nextInt() - 1;
			int r = nextInt() - 1;
			int x = nextInt();

			int[] max = maxQuery(l,r + 1,0,0,M + 1);
			int[] min = minQuery(l,r + 1,0,0,M + 1);

			if(max[0] != x){
				out.println(max[1] + 1);
			}else if(min[0] != x){
				out.println(min[1] + 1);
			}else{
				out.println(-1);
			}
		}
	}

	public static void main(String[] args) {
		out.flush();
		new C().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}