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:
//package CF;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class A {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt(), m = sc.nextInt();
		int [] a = new int[n];
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
		}
		SparseTable stMin = new SparseTable(a, true);
		SparseTable stMax = new SparseTable(a, false);
		while(m-->0){
			int l = sc.nextInt()-1, r = sc.nextInt()-1, x = sc.nextInt();
			int min = stMin.query(l, r, true);
			if(x == a[min]){
				int max = stMax.query(l, r, false);
				if(x == a[max])
					out.println(-1);
				else out.println(max+1);
			}
			else out.println(min+1);
		}
		out.flush();
		out.close();
	}
	static class SparseTable {                                          

		int A[], SpT[][];

		SparseTable(int[] A, boolean min) 
		{
			int n = A.length;	this.A = A;
			int k = (int)Math.floor(Math.log(n) / Math.log(2)) + 1;
			SpT = new int[n][k];

			for (int i = 0; i < n; i++) 
				SpT[i][0] = i; 					// RMQ of sub array starting at index i and of length 2^0=1

			//overall time complexity = O(n log n)
			for (int j = 1; (1<<j) <= n; j++) 				
				for (int i = 0; i + (1<<j) - 1 < n; i++)
					if(min)
						if (A[SpT[i][j-1]] < A[SpT[i+(1<<(j-1))][j-1]])
							SpT[i][j] = SpT[i][j-1];    		// start at index i of length 2^(j-1)
						else                  					// start at index i+2^(j-1) of length 2^(j-1)
							SpT[i][j] = SpT[i+(1<<(j-1))][j-1];
					else 
						if (A[SpT[i][j-1]] > A[SpT[i+(1<<(j-1))][j-1]])
							SpT[i][j] = SpT[i][j-1];    		// start at index i of length 2^(j-1)
						else                  					// start at index i+2^(j-1) of length 2^(j-1)
							SpT[i][j] = SpT[i+(1<<(j-1))][j-1];
		}

		int query(int i, int j, boolean min) 
		{

			int k = (int)Math.floor(Math.log(j-i+1) / Math.log(2)); // 2^k <= (j-i+1)
			if(min)
				if (A[SpT[i][k]] <= A[SpT[j-(1<<k)+1][k]]) 
					return SpT[i][k];
				else
					return SpT[j-(1<<k)+1][k];
			else 
				if (A[SpT[i][k]] >= A[SpT[j-(1<<k)+1][k]]) 
					return SpT[i][k];
				else
					return SpT[j-(1<<k)+1][k];
		} 
	}
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(FileReader fileReader) {
			br = new BufferedReader(fileReader);
		}

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

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}