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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;



public class C {
	
	static class Scanner{
		BufferedReader br=null;
		StringTokenizer tk=null;
		public Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		public String next() throws IOException{
			while(tk==null || !tk.hasMoreTokens())
				tk=new StringTokenizer(br.readLine());
			return tk.nextToken();
		}
		public int nextInt() throws NumberFormatException, IOException{
			return Integer.valueOf(next());
		}
		public long nextLong() throws NumberFormatException, IOException{
			return Long.valueOf(next());
		}
		public double nextDouble() throws NumberFormatException, IOException{
			return Double.valueOf(next());
		}
	}
	
	
	static class Intervalo implements Comparable<Intervalo>{
		int l, r;
		public Intervalo(int ll, int rr) {
			l = ll;
			r = rr;
		}
		@Override
		public int compareTo(Intervalo o) {
			return l - o.l;
		}
		public String toString() {
			return "(" + l + "," + r + ")";
		}
	}
	
	static int N, M;
	
	static HashMap<Integer, ArrayList<Integer> > map;
	static HashMap<Integer, TreeSet<Intervalo> > map2;
	
	
	public static void main(String args[]) throws NumberFormatException, IOException {
		Scanner sc = new Scanner();
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = sc.nextInt();
		M = sc.nextInt();
		map = new HashMap<Integer, ArrayList<Integer> >();
		for(int i = 0; i < N; i++) {
			int n = sc.nextInt();
			if (!map.containsKey(n))
				map.put(n, new ArrayList<Integer>());
			map.get(n).add(i);
		}
		map2 = new HashMap<Integer, TreeSet<Intervalo> >();
		for(int n: map.keySet()) {
			ArrayList<Integer> c = map.get(n);
			TreeSet<Intervalo> set = new TreeSet<Intervalo>();
			int first = -1;
			int last = -1;
			for(int idx:  c) {
				if (first == -1)
					first = idx;
				else {
					if (idx > last + 1) {
						set.add(new Intervalo(first, last));
						first = idx;
					}
				}
				last = idx;
			}
			set.add(new Intervalo(first, last));
			map2.put(n, set);
		}
		for(int i = 0; i < M; i++) {
			int l  = sc.nextInt() - 1;
			int r = sc.nextInt() - 1;
			int x = sc.nextInt();
			if (!map2.containsKey(x))
				bw.write((l + 1) + "\n");
			else {
				TreeSet<Intervalo> s = map2.get(x);
				Intervalo inter = s.floor(new Intervalo(l, 0));
				if (inter == null)
					bw.write((l + 1) + "\n");
				else {
					if (inter.r < l)
						bw.write((l + 1) + "\n");
					else if (inter.r + 1 <= r)
						bw.write((inter.r + 2) + "\n");
					else
						bw.write((-1) + "\n");
				}
			}
		}
		bw.flush();
	}

}