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

public class Div2_622C {
	public static int[] arr;

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

	public Div2_622C() 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());
		arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = Integer.parseInt(st.nextToken()) - 1;
		Tree tree = new Tree(0, n - 1);
		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;

			Value res = tree.root.query(l, r, x);
			if (res == null) {
				out.println("-1");
			} else {
				out.println(res.position + 1);
			}
		}
		out.flush();
	}

	class Tree {
		Node root;

		public Tree(int min, int max) {
			this.root = new Node(min, max);
		}

		class Node {
			Node left, right;
			Value minVal, maxVal;
			int min, max;

			public Node(int min, int max) {
				this.min = min;
				this.max = max;
				if (min != max) {
					this.left = new Node(min, (min + max) / 2);
					this.right = new Node((min + max) / 2 + 1, max);
					this.minVal = this.left.minVal;
					if (this.minVal.value == -1 || this.right.minVal.compareTo(this.minVal) < 0)
						this.minVal = this.right.minVal;
					this.maxVal = this.left.maxVal;
					if (this.maxVal.value == -1 || this.right.maxVal.compareTo(this.maxVal) > 0)
						this.maxVal = this.right.maxVal;
				} else {
					int tmp = arr[min];
					this.minVal = this.maxVal = new Value(tmp, min);
				}
			}

			public Value query(int qmin, int qmax, int target) {
				if (min >= qmin && max <= qmax) {
					if (this.minVal.value != -1 && this.minVal.value != target)
						return this.minVal;
					if (this.maxVal.value != -1 && this.maxVal.value != target)
						return this.maxVal;
					return null;
				}
				Value answer = null;
				
				if (answer == null)
					if (qmax >= left.min && qmin <= left.max)
						answer = left.query(qmin, qmax, target);
				
				if (answer == null)
					if (qmax >= right.min && qmin <= right.max)
						answer = right.query(qmin, qmax, target);
				
				return answer;
			}
		}
	}

	class Value implements Comparable<Value> {
		int value;
		int position;

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

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

	}
}