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.Arrays;
import java.util.StringTokenizer;

public class RMQTest {

	public static void main(String[] args) throws IOException {
		new RMQTest();
	}

	public RMQTest() throws IOException {
		PrintWriter out = new PrintWriter(System.out);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st
				.nextToken());
		st = new StringTokenizer(br.readLine());
		ValueMin[] minValArr = new ValueMin[n];
		ValueMax[] maxValArr = new ValueMax[n];
		for (int i = 0; i < n; i++)
			minValArr[i] = new ValueMin(Integer.parseInt(st.nextToken()) - 1, i);
		for (int i = 0; i < n; i++)
			maxValArr[i] = new ValueMax(minValArr[i].value, i);
		RMQ<ValueMin> rangeMinQuery = new RMQ<>(minValArr);
		RMQ<ValueMax> rangeMaxQuery = new RMQ<>(maxValArr);
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken()) - 1, r = Integer
					.parseInt(st.nextToken()) - 1, x = Integer.parseInt(st
					.nextToken()) - 1;

			ValueMin min = rangeMinQuery.query(l, r);
			ValueMax max = rangeMaxQuery.query(l, r);
			Value res = min.value == x ? (max.value == x ? null : max) : min;
			if (res == null) {
				out.println("-1");
			} else {
				out.println(res.position + 1);
			}
		}
		out.flush();

	}

	class RMQ<T extends Comparable<T>> {

		private Object[][] table; // [n][log(n)]

		public RMQ(T[] array) {
			int n = array.length;
			int log = Integer.numberOfTrailingZeros(Integer.highestOneBit(n));
			table = new Object[n][log + 1];
			for (int i = 0; i < n; i++) {
				table[i][0] = array[i];
			}
			int logsize = 1;
			for (int j = 1; j <= log; j++) {
				for (int i = 0; i < n; i++) {
					// System.out.print("table[" + i + "][" + j + "]=min(" +
					// table[i][j-1]);
					table[i][j] = table[i][j - 1];
					if (i + logsize < n) {
						// System.out.print(", " + table[i+logsize][j-1]);
						if (((T) table[i + logsize][j - 1])
								.compareTo((T) table[i][j]) < 0)
							table[i][j] = table[i + logsize][j - 1];
					}
					// System.out.println(") [" + i + "][" + (j-1) + "] or [" +
					// (i+logsize) + "][" + (j-1) + "]");
				}
				logsize <<= 1;
			}
		}

		// {a,b,c,d,e}
		public T query(int min, int max) {
			int range = max - min + 1;
			int rangeLogVal = Integer.highestOneBit(range);
			//System.out.println("Range: " + range);
			//System.out.println("Val: " + rangeLogVal);
			int rangeLog = Integer.numberOfTrailingZeros(rangeLogVal);
			T answer1 = (T) table[min][rangeLog];
			T answer2 = (T) table[max - rangeLogVal + 1][rangeLog];
			//System.out.println("table[" + min + "][" + rangeLog + "]="
			//		+ answer1);
			//System.out.println("table[" + (max - rangeLogVal + 1) + "]["
			//		+ rangeLog + "]=" + answer2);
			if (answer1.compareTo(answer2) < 0)
				return answer1;
			return answer2;
		}
	}

	class Value {
		int value;
		int position;

		public Value(int value, int position) {
			this.value = value;
			this.position = position;
		}
	}

	class ValueMin extends Value implements Comparable<ValueMin> {
		public ValueMin(int value, int position) {
			super(value, position);
		}

		@Override
		public int compareTo(ValueMin o) {
			return Integer.compare(value, o.value);
		}

	}

	class ValueMax extends Value implements Comparable<ValueMax> {
		public ValueMax(int value, int position) {
			super(value, position);
		}

		@Override
		public int compareTo(ValueMax o) {
			return -Integer.compare(value, o.value);
		}

	}
}