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.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.security.interfaces.DSAKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class a {

	public static class point {
		int val1;
		int val2;
		int pos1;
		int pos2;
		boolean ok;

		point(int v1, int v2, int p1, int p2, boolean o) {
			val1 = v1;
			val2 = v2;
			pos1 = p1;
			pos2 = p2;
			ok = o;
		}

		point() {
		}

	}

	public static class in {
		static BufferedReader reader;
		static StringTokenizer tokenizer;

		static void init(InputStream input) {
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}

		static String next() throws IOException {
			while (!tokenizer.hasMoreTokens())
				tokenizer = new StringTokenizer(reader.readLine());
			return tokenizer.nextToken();
		}

		static int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		static double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		static long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}

	public static point tree[];
	public static int a[];

	public static point form(point p, point p1, point p2) {
		if (p1.ok) {
			return p1;
		} else if (p2.ok)
			return p2;
		else {
			if (p1.val1 != p2.val1) {
				p = new point(p1.val1, p2.val1, p1.pos1, p2.pos1, true);
				return p;
			} else {

				return p1;
			}
		}
	}

	public static void build(int s, int e, int p) {

		if (s == e) {
			tree[p] = new point(a[s], -1, s, -1, false);

			return;
		}
		tree[p] = new point();
		int mid = (s + e) / 2;

		build(s, mid, p * 2);
		build(mid + 1, e, p * 2 + 1);
		tree[p] = form(tree[p], tree[p * 2], tree[p * 2 + 1]);

	}

	public static point get(int s, int e, int p, int from, int to) {

		if (s >= from && e <= to) {
			return tree[p];

		}

		int mid = (s + e) / 2;

		if (to <= mid) {
			point a = get(s, mid, p * 2, from, to);
			return a;
		} else if (from > mid) {
			point b = get(mid + 1, e, p * 2 + 1, from, to);
			return b;
		} else {
			point a = get(s, mid, p * 2, from, to);
			point b = get(mid + 1, e, p * 2 + 1, from, to);
			point ans = new point();
			ans = form(ans, a, b);
			return ans;
		}

	}

	public static void main(String[] args) throws IOException {
		in.init(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		int m = in.nextInt();
		a = new int[n + 1];
		tree = new point[n * 4 + 10];

		for (int i = 0; i < n; i++) {
			a[i + 1] = in.nextInt();
		}
		build(1, n, 1);

		for (int i = 0; i < m; i++) {
			int l = in.nextInt();
			int r = in.nextInt();
			int x = in.nextInt();
			point ans = get(1, n, 1, l, r);
			if (ans.val1 != x)
				out.println(ans.pos1);

			else if (ans.val2 != x)
				out.println(ans.pos2);

			else
				out.println(-1);

		}
		out.close();

	}
}