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

public class prog {
	class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public MyScanner(String name) {
			try {
				br = new BufferedReader(new FileReader(name));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public String nextToken() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

		public long nextLong() {
			return Long.parseLong(nextToken());
		}

		public double nextDouble() {
			return Double.parseDouble(nextToken());
		}
	}

	public void run() {
		try {
			// Scanner in = new Scanner(System.in);
			MyScanner in = new MyScanner();
			PrintWriter out = new PrintWriter(System.out);
			int n = in.nextInt();
			int k = in.nextInt();

			int[] arr = new int[n];

			int N2 = 131072 * 2;

			int[] tree_min = new int[2 * N2];
			int[] tree_max = new int[2 * N2];

			for (int i = 0; i < n; i++) {
				int a = in.nextInt();
				tree_max[N2 + i + 1] = i;
				tree_min[N2 + i + 1] = i;
				arr[i] = a;
			}

			for (int v = N2 - 1; v > 0; v--) {
				if (arr[tree_max[2 * v]] > arr[tree_max[2 * v + 1]]) {
					tree_max[v] = tree_max[2 * v];
				} else {
					tree_max[v] = tree_max[2 * v + 1];
				}

				if (arr[tree_min[2 * v]] > arr[tree_min[2 * v + 1]]) {
					tree_min[v] = tree_min[2 * v + 1];
				} else {
					tree_min[v] = tree_min[2 * v];
				}
			}

			for (int i = 0; i < k; i++) {
				int l = in.nextInt();
				int r = in.nextInt();

				int x = in.nextInt();

				int min = get_min(l, r, tree_min, N2, arr);
				
				int max = get_max(l, r, tree_max, N2, arr);

				if (arr[min] == x) {
					if (arr[max] == x) {
						out.println(-1);
					} else {
						out.println(max + 1);
					}
				} else {
					out.println(min + 1);
				}
			}
			out.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	private int get_max(int left, int right, int[] tree_max, int n, int[] arr) {
		left += n;
		right += n;
		
		int res = left - n - 1;

		while (left <= right) {
			if (left % 2 == 1) {
				if (arr[tree_max[left]] > arr[res]) {
					res = tree_max[left];
				}
				left++;
			}
			if (right % 2 == 0) {
				if (arr[tree_max[right]] > arr[res]) {
					res = tree_max[right]; 
				}
				right--;
			}
			
			left /= 2;
			right /= 2;
		}
		return res;

	}

	private int get_min(int left, int right, int[] tree_min, int n, int[] arr) {
		left += n;
		right += n;

		int res = left - n - 1;

		while (left <= right) {
			if (left % 2 == 1) {
				if (arr[tree_min[left]] < arr[res]) {
					res = tree_min[left];
				}
				left++;
			}
			if (right % 2 == 0) {
				if (arr[tree_min[right]] < arr[res]) {
					res = tree_min[right];
				}
				right--;
			}

			left /= 2;
			right /= 2;
		}
		return res;
	}

	public static void main(String[] args) throws FileNotFoundException {
		new prog().run();
	}
}