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.util.*;
import java.io.*;

public class C{
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		Solver solver = new Solver();
		solver.solve(in, out);
		out.close();	
	}

	static class Solver{
		int n, m;
		int[] a, next;

		public void solve(InputReader in, PrintWriter out) {
			init(in);
			int i = 0, j = 0;
			while (i < n) {
				while (j < n && a[i] == a[j]) ++j;
				next[i] = j;
				++i;
			}
			for (int k = 0; k < m; ++ k) {
				int l = in.nextInt()-1, r = in.nextInt()-1, x = in.nextInt();
				int ans = -1;
				if (a[l] != x) ans = l+1;
				else if (next[l] <= r) ans = next[l]+1;
				out.println(ans);
			}
		}

		void init(InputReader in) {
			n = in.nextInt();
			m = in.nextInt();
			a = new int[n];
			next = new int[n+1];
			next[n] = -1;
			for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
		}
	}

	static class InputReader{
		BufferedReader reader;
		StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try{
					tokenizer = new StringTokenizer(reader.readLine());
				} catch(IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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