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 Main {
	class InputReader {
	    
		private BufferedInputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(BufferedInputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public String readLine(){
			int c=read();
			StringBuilder res = new StringBuilder();
			while (c!=10){
			
				res.appendCodePoint(c);
				c = read();
			} 
			//System.out.println("***"+res.toString());
			return res.toString();
		}
		public String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public String next() {
			return readString();
		}

		
	}

	class OutputWriter {
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}

		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}

		public void print(Object...objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		public void printLine(Object...objects) {
			print(objects);
			writer.println();
		}

		public void close() {
			writer.close();
		}

		public void flush() {
			writer.flush();
		}

		}

	class Node{
		int st,en,min,max;
		Node left,right;
		void set(int a,int b,int c,int d)
		{
			st= a;
			en=b;
			min=c;
			max=d;
			//System.out.println("st"+st+" en"+ en+" min"+min+" max"+max);
		}
	}
	Node makeTree(int[] a ,int st,int en)
	{
		if(st>en) return null;
		Node node= new Node();
		if(st==en) 
		{
			node.set(st, st, st, st);
			node.left=null;
			node.right=null;
			return node;
		}
		int mid = (st+en)/2;
		node.left = makeTree(a, st, mid);
		node.right=makeTree(a, mid+1, en);
		int minm = ( (a[node.left.min]<a[node.right.min]?node.left.min:node.right.min));
		int maxm = ((a[node.left.max]>a[node.right.max]?node.left.max:node.right.max));

		node.set(st, en, minm, maxm);
		return node;
	}

public static void main(String[] args) throws IOException
{
	Main m =new Main();
	InputReader r = m.new InputReader(new BufferedInputStream(System.in));
	PrintWriter pw=  new PrintWriter(System.out);
	int n = r.readInt();
	int q = r.readInt();
	int[]  a = new int[n];
	for(int i=0;i<n;i++) a[i] = r.readInt();
	
	Node root = m.makeTree(a,0,n-1);
	for(;q>0;q--)
	{
		int l=r.readInt(),rt = r.readInt(), x=r.readInt();
		l--;
		rt--;
		int k = m.traverse(a,root,l,rt,x);
		pw.println(k==-1?k:k+1);
	}
	pw.close();
	return;
}
private int traverse(int[] a,Node root,int l,int r,int x) {
	
	if(root.st==l && root.en==r) return a[root.max]!=x?root.max:(a[root.min]!=x?root.min:-1);
	if(root.left!=null && root.left.en>=r)
	{
		return traverse(a,root.left,l,r,x);
	}
	else if(root.right!=null&& root.right.st<=l)
	{
		return traverse(a,root.right,l,r,x);

	}
	else
	{
		int t1= traverse(a,root.left, l, (root.left.en), x);
		if(t1!=-1) return t1;
		int t2 = traverse(a,root.right, (root.right.st), r, x);
		return t2;
	}
}
}