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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class muyrapido {


	
	public static void main(String[] args) throws IOException {
		BufferedReader bu = new BufferedReader(new InputStreamReader(System.in));
		
		PrintWriter out = new PrintWriter(System.out);

		StringTokenizer tok1 = new StringTokenizer(bu.readLine(), " ");
//		String[] l1 = bu.readLine().split(" ");

		int n = Integer.parseInt(tok1.nextToken());//Integer.parseInt(l1[0]);
		int m =  Integer.parseInt(tok1.nextToken());//Integer.parseInt(l1[1]);

		StringTokenizer tokenizer = new StringTokenizer(bu.readLine(), " ");
//		String[] in = bu.readLine().split(" ");

		int[] i = new int[n];

		int c = 0;


		
		while (tokenizer.hasMoreTokens()) {
			i[c] = Integer.parseInt(tokenizer.nextToken());
			//			System.out.println(i[c]);
			c++;
		}
		
		int[] next = new int[n];
		next[n-1] = n;
		
		for (int q = n-2; q >= 0; q--) {
			if (i[q] != i[q+1]) {
				next[q] = q+1;
			}else {
				next[q] = next[q+1];
			}
		}

		ArrayList<int[]> list = new ArrayList<>();

		int[] outArray = new int[m];

		for (int a = 0; a < m; a++) {
			//String[] line= bu.readLine().split(" ");
			StringTokenizer inner = new StringTokenizer(bu.readLine(), " ");

			outArray[a] = -1;
			

				list.add(new int[5]);
				list.get(a)[0] = Integer.parseInt(inner.nextToken())-1;
				list.get(a)[1] = Integer.parseInt(inner.nextToken())-1;
				list.get(a)[2] = Integer.parseInt(inner.nextToken());
				list.get(a)[3] = -1;
				list.get(a)[4] = a;
			
			//System.out.println(queries[a][0] + " " + queries[a][1] + " " + queries[a][2]);


		}
		
		for (int a = 0; a < list.size(); a++) {
	
			for (int aa = list.get(a)[0]; aa <= list.get(a)[1]; aa = next[aa]) {
				if (i[aa] != list.get(a)[2]) {

					//list.get(0)[3] = aa+1;
					outArray[list.get(a)[4]] = aa+1;
					break;
				}
			}
		}

//		int cm = m;
//
//
//		for (int z = 0; z < n; z = next[z]) {
//
//
//
//			for (int zz = 0; zz < cm; zz++) {
//
//				if (i[z] != list.get(zz)[2] && z >= list.get(zz)[0] && z <= list.get(zz)[1]) {
//					list.get(zz)[3] = z;
//					outArray[list.get(zz)[4]] = list.get(zz)[3]+1;
//					list.remove(zz);
//					zz--;
//					cm--;
//				}
//			}
//
//			if (cm <= 0) break;
//		}

		for (int z = 0; z < m; z++) {
			out.println(outArray[z]);
		}

		out.close();


	}

	


}