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.InputStream;
	import java.io.InputStreamReader;
	import java.io.PrintWriter;
	import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
	import java.util.Set;
	import java.util.StringTokenizer;
	import java.util.TreeMap;
	import java.util.TreeSet;
	
	public class a1 {
		static long val[];
		static int weight[];
		static int memo[][];
		static int n;

		
		public static void main(String[] args) throws IOException {
			// TODO Auto-generated method stub
		
			
				Scanner sc = new Scanner(System.in);
				PrintWriter out =new PrintWriter(System.out);
				int n=sc.nextInt();
				int q=sc.nextInt();
				int[]a=new int[n];
				int nextnotequal[]=new int [n];
				a[0]=sc.nextInt();
				int pointer=0;
				for(int i=1;i<n;i++) {					
					a[i]=sc.nextInt();
					if(a[i]==a[i-1]) continue;
					
						for(int j=i-1;j>=pointer;j--) {
							nextnotequal[j]=i;
					}
						pointer=i;
					
				}
				for(int i=n-1;i>=pointer;i--) {
					nextnotequal[i]=-1;
				}
               // System.out.println(Arrays.toString(nextnotequal));
				
				while(q-->0) {
					int l=sc.nextInt()-1;
					int r=sc.nextInt()-1;
					int x=sc.nextInt();
					
					int ans=-1;
					if(a[l]!=x)ans=l+1;
					else if(nextnotequal[l]>=l&&nextnotequal[l]<=r)ans=nextnotequal[l]+1;
					 out.println(ans);
					}
				out.close();
				
			
		}
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		static class point{
			int x;
			int y;
			public point(int x,int y) {
				this.x=x;
				this.y=y;
			}
			int eqdist(point p){
				return (int) Math.sqrt((this.x-p.x)*(this.x-p.x)+(this.y-p.y)*(this.y-p.y));
			}
		}
		static class Scanner {

	        BufferedReader br;
	        StringTokenizer st;

	        Scanner(InputStream system) {
	            br = new BufferedReader(new InputStreamReader(system));
	        }

	        String next() throws IOException {
	            while (st == null || !st.hasMoreTokens())
	                st = new StringTokenizer(br.readLine());
	            return st.nextToken();
	        }

	        int nextInt() throws IOException {
	            return Integer.parseInt(next());
	        }

	        double nextDouble() throws IOException {
	            return Double.parseDouble(next());
	        }

	        long nextLong() throws IOException {
	            return Long.parseLong(next());
	        }


	    }

	}