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

public class Edu7C {
	static class RmqSparseTable {
		int n, A[], logTable[], M[][];

		public RmqSparseTable(int A[]) {
			this.A = A;
			this.n = A.length;
			init();
		}

		private void init() {
			logTable = new int[n + 1];
			for (int i = 2; i <= n; i++) {
				logTable[i] = logTable[i >> 1] + 1;
			}
			M = new int[logTable[n] + 1][n];
			for (int i = 0; i < n; i++) {
				M[0][i] = i;
			}
			for (int k = 1; (1 << k) < n; k++) {
				for (int i = 0; (1 << k) + i <= n; i++) {
					int x = M[k - 1][i];
					int y = M[k - 1][i + (1 << k - 1)];
					M[k][i] = A[x] <= A[y] ? x : y;
				}
			}
		}

		/**
		 * 
		 * @param l
		 *            Zero Based
		 * @param r
		 *            Zero BFased
		 * @return index of the minimum element between l - r
		 */
		int RMQ(int l, int r) {
			int k = logTable[r - l];
			int left = M[k][l];
			int right = M[k][r - (1 << k) + 1];
			return A[left] < A[right] ? left : right;
		}
	}

	static class RmqSparseTable2 {
		int n, A[], logTable[], M[][];

		public RmqSparseTable2(int A[]) {
			this.A = A;
			this.n = A.length;
			init();
		}

		private void init() {
			logTable = new int[n + 1];
			for (int i = 2; i <= n; i++) {
				logTable[i] = logTable[i >> 1] + 1;
			}
			M = new int[logTable[n] + 1][n];
			for (int i = 0; i < n; i++) {
				M[0][i] = i;
			}
			for (int k = 1; (1 << k) < n; k++) {
				for (int i = 0; (1 << k) + i <= n; i++) {
					int x = M[k - 1][i];
					int y = M[k - 1][i + (1 << k - 1)];
					M[k][i] = A[x] >= A[y] ? x : y;
				}
			}
		}

		/**
		 * 
		 * @param l
		 *            Zero Based
		 * @param r
		 *            Zero BFased
		 * @return index of the minimum element between l - r
		 */
		int RMQ(int l, int r) {
			int k = logTable[r - l];
			int left = M[k][l];
			int right = M[k][r - (1 << k) + 1];
			return A[left] > A[right] ? left : right;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String[] l = bf.readLine().split(" ");
		int n = Integer.parseInt(l[0]);
		int m = Integer.parseInt(l[1]);
		l = bf.readLine().split(" ");
		int arr[] = new int[n];
		for (int i = 0; i < l.length; i++) {
			arr[i] = Integer.parseInt(l[i]);
		}
		RmqSparseTable rminq = new RmqSparseTable(arr);
		RmqSparseTable2 rmaxq = new RmqSparseTable2(arr);
		int a, b, c, minInd, maxInd;
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < m; i++) {
			l = bf.readLine().split(" ");
			a = Integer.parseInt(l[0]) - 1;
			b = Integer.parseInt(l[1]) - 1;
			c = Integer.parseInt(l[2]);
			minInd = rminq.RMQ(a, b);
			maxInd = rmaxq.RMQ(a, b);
			if (arr[minInd] == c && arr[maxInd] == c) {
				sb.append(-1 + "\n");
			} else {
				if (arr[minInd] == c)
					sb.append((maxInd + 1) + "\n");
				else
					sb.append((minInd + 1) + "\n");
			}
		}
		System.out.print(sb);
	}
}