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

public class TheTime {
	
	static int bs (ArrayList <Integer> a , int r1 , int r2) 
	{
		int lo = 0; 
		int hi = a.size()-1;
		int ans = -1;
		while(lo <= hi)
		{
			int mid = lo + (hi-lo)/2;
			int k = a.get(mid);
			if( (k <= r2 && k>= r1) || (k == r1) || (k == r2))
			{
				ans = k;
				break;
			}
			else if(k > r2)
			{
				hi = mid - 1;
			}
			else if(k < r1)
				lo = mid + 1;
		}
		return ans;
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = sc.nextInt();
		int m = sc.nextInt();
		int a [] = new int[n];
		int maxNum = Integer.MIN_VALUE;
		int minNum = Integer.MAX_VALUE;
		int [] A = new int [a.length + 7];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
			maxNum = Math.max(maxNum, a[i]);
			minNum = Math.min(minNum, a[i]);
			A[i] = a[i];
		}
		
		ArrayList<Integer> [] pos = new ArrayList[maxNum + 1];
		for (int i = 0; i < n; i++) {
			if(pos[a[i]] == null)
			{
				pos[a[i]] = new ArrayList<Integer>();
			} 
			pos[a[i]].add(i);
		}
		SegmentTreeMin stMin = new SegmentTreeMin(A);
		SegmentTreeMax  stMax = new SegmentTreeMax(A);
		while(m -- > 0)
		{
			int l = sc.nextInt() - 1;
			int e = sc.nextInt() - 1;
			int x = sc.nextInt();
			int curMin = a[stMin.rmq(l, e)];
			int curMax = a[stMax.rmq(l, e)];
			int p = -1;
			if(curMax != x)
			{
				if(pos[curMax].size() != 0)
				{
					p = bs(pos[curMax],l,e);
				}
			}
			else
				if(curMin != x)
				{
					if(pos[curMin].size() != 0)
					{
						p = bs(pos[curMin],l,e);
					}
				}
			sb.append((p != -1 ? (p+1) : -1)).append("\n");
		}
		System.out.print(sb);
	}
	
	
	static class SegmentTreeMin {
		private int[] st, A;
		private int n;

		private int left(int p) {
			return p << 1;
		}

		private int right(int p) {
			return (p << 1) + 1;
		}

		private void build(int p, int L, int R) {
			if (L == R)
				st[p] = L;
			else {
				build(left(p), L, (L + R) / 2);
				build(right(p), (L + R) / 2 + 1, R);
				int p1 = st[left(p)], p2 = st[right(p)];
				st[p] = (A[p1] <= A[p2]) ? p1 : p2;
			}
		}

		private int rmq(int p, int L, int R, int i, int j) {
			if (i > R || j < L)
				return -1;
			if (L >= i && R <= j)
				return st[p];

			int p1 = rmq(left(p), L, (L + R) / 2, i, j);
			int p2 = rmq(right(p), (L + R) / 2 + 1, R, i, j);

			if (p1 == -1)
				return p2;
			if (p2 == -1)
				return p1;
			return (A[p1] <= A[p2]) ? p1 : p2;
		}

		public SegmentTreeMin(int[] _A) {
			A = _A;
			n = A.length;
			st = new int[4 * n];
			for (int i = 0; i < 4 * n; i++)
				st[i] = 0;
			build(1, 0, n - 1);
		}

		public int rmq(int i, int j) {
			return rmq(1, 0, n - 1, i, j);
		}
	}
	
	static class SegmentTreeMax {
		private int[] st, A;
		private int n;

		private int left(int p) {
			return p << 1;
		}

		private int right(int p) {
			return (p << 1) + 1;
		}

		private void build(int p, int L, int R) {
			if (L == R)
				st[p] = L;
			else {
				build(left(p), L, (L + R) / 2);
				build(right(p), (L + R) / 2 + 1, R);
				int p1 = st[left(p)], p2 = st[right(p)];
				st[p] = (A[p1] >= A[p2]) ? p1 : p2;
			}
		}

		private int rmq(int p, int L, int R, int i, int j) {
			if (i > R || j < L)
				return -1;
			if (L >= i && R <= j)
				return st[p];

			int p1 = rmq(left(p), L, (L + R) / 2, i, j);
			int p2 = rmq(right(p), (L + R) / 2 + 1, R, i, j);

			if (p1 == -1)
				return p2;
			if (p2 == -1)
				return p1;
			return (A[p1] >= A[p2]) ? p1 : p2;
		}

		public SegmentTreeMax(int[] _A) {
			A = _A;
			n = A.length;
			st = new int[4 * n];
			for (int i = 0; i < 4 * n; i++)
				st[i] = 0;
			build(1, 0, n - 1);
		}

		public int rmq(int i, int j) {
			return rmq(1, 0, n - 1, i, j);
		}

	}

	
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		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();
		}

	}

}