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




public class C { 
	
	static class Query { 
		
		int from, to, num;
		
		public Query(int from, int to, int num) { 
			this.from = from;
			this.to = to;
			this.num = num;
		}
	}
	static class Segment { 
		int begin, end;
		int num;
		public Segment(int begin, int end, int num) { 
			this.begin = begin;	
			this.end  = end;
			this.num = num;
		}
		
		@Override
		public String toString() { 
			return String.format("from: %d to: %d num: %d", begin, end, num);
		}
	}
	
	static List<Segment> segments = new ArrayList<Segment>();
	public static void main(String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(tokenizer.nextToken());
		int M = Integer.parseInt(tokenizer.nextToken());
		
		tokenizer = new StringTokenizer(br.readLine());

		
		int begin = -1;
		int end = -1;

		int prevNum = -1;
		int num = -1;
		
		for(int i=0; i<N; i++) { 
			num = Integer.parseInt(tokenizer.nextToken());
			if(i == 0) { 
				prevNum = num;
				begin = 0;
				end = 1;
			} else { 
				if(prevNum == num) end++; 
				else { 
					Segment newSegment = new Segment(begin, end-1, prevNum);
					segments.add(newSegment);
					begin = i;
					end = i+1;
					prevNum = num;
				}
			}
		}

		Segment newSegment = new Segment(begin, end-1, prevNum);
		segments.add(newSegment);
		
		
		List<Query> queries = new ArrayList<Query>();

		for(int i=0; i<M; i++) { 
			tokenizer = new StringTokenizer(br.readLine());
			int from = -1 + Integer.parseInt(tokenizer.nextToken());
			int to = -1 + Integer.parseInt(tokenizer.nextToken());
			num = Integer.parseInt(tokenizer.nextToken());
			
			Query newQuery = new Query(from, to, num);
			queries.add(newQuery);
		}
		
		
		List<Integer> sol = new ArrayList<Integer>();
		
		
		for(Query query : queries) { 
			int from = query.from;
			int to = query.to;
			num = query.num;
			
			
			if(segments.size() == 1) { 
				if(num == segments.get(0).num) { 
					sol.add(-1);
				} else { 
					sol.add(1 + from);
				}
				continue;
			}
			
			int seg_ind = -1;//binarySearch(0, segments.size()-1, from, to);
			
			int ss = 0, ee = segments.size()-1;
			
		
			
			while(ss <= ee) { 
				int m = (ss + ee) / 2;
				
				if(segments.get(m).begin > from) { 
					ee = m - 1;
				} else { 
					if(segments.get(m).end < from) { 
						ss = m + 1;
					} else { 
						seg_ind = m;
						break;
					}
					
				}
				
			}

			Segment s = segments.get(seg_ind);

			if(s.num == num) { 
				if(s.end >= to) { 
					sol.add(-1);
					//System.out.println(-1);
				} else { 
					//System.out.println(1 + s.end + 1);
					sol.add(1 + s.end + 1);
				}
			} else { 
				//System.out.println(1 + from);	
				sol.add(1 + from);
			}

		}
		
		for(Integer s : sol) { 
			//System.out.println(s);
			bw.write("" + s);
			bw.newLine();
		}
		
		bw.flush();
		bw.close();

				
	}
	
}