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

public class CF622C {
	static int[] aa, max, min;
	static void build(int k, int l, int r) {
		if (r - l == 1) {
			max[k] = min[k] = l;
			return;
		}
		int m = (l + r) / 2;
		build(k * 2 + 1, l, m);
		build(k * 2 + 2, m, r);
		int min1 = min[k * 2 + 1];
		int min2 = min[k * 2 + 2];
		min[k] = aa[min1] <= aa[min2] ? min1 : min2;
		int max1 = max[k * 2 + 1];
		int max2 = max[k * 2 + 2];
		max[k] = aa[max1] >= aa[max2] ? max1 : max2;
	}
	static void query(int k, int l, int r, int ql, int qr, int[] mm) {
		if (qr <= l || r <= ql)
			return;
		if (ql <= l && r <= qr) {
			if (mm[0] == -1 || aa[mm[0]] > aa[min[k]])
				mm[0] = min[k];
			if (mm[1] == -1 || aa[mm[1]] < aa[max[k]])
				mm[1] = max[k];
			return;
		}
		int m = (l + r) / 2;
		query(k * 2 + 1, l, m, ql, qr, mm);
		query(k * 2 + 2, m, r, ql, qr, mm);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = Integer.parseInt(st.nextToken());
		max = new int[n * 4];
		min = new int[n * 4];
		build(0, 0, n);
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int[] mm = new int[] { -1, -1 };
			query(0, 0, n, l - 1, r, mm);
			int p = -1;
			if (aa[mm[0]] != x)
				p = mm[0] + 1;
			else if (aa[mm[1]] != x)
				p = mm[1] + 1;
			pw.println(p);
		}
		pw.close();
	}
}