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.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main
{

	/* IO */
	InputReader in;
	StringTokenizer tok;
	StringBuilder ans;

	/* FIELDS */
	int n;
	int[] arr;

	public static void main(String[] args) throws FileNotFoundException
	{
		Main sol = new Main();
		sol.begin();

	}

	private void begin() throws FileNotFoundException
	{
		// io
		boolean file = false;
		if (file)
			in = new InputReader(new FileInputStream("input.txt"));
		else
			in = new InputReader(System.in);
		ans = new StringBuilder();

		// read
		n = in.nextInt();
		int nQuries = in.nextInt();
		arr = new int[n + 1];
		for (int i = 0; i < n; i++)
			arr[i] = in.nextInt();

		// precompute
		int last = n;
		int next[] = new int[n + 1];
		for (int i = n - 1; i >= 0; i--)
			if (arr[i] != arr[i + 1])
			{
				next[i] = i + 1;
				last = i + 1;
			} else
				next[i] = last;

		// take queries
		for (int i = 0; i < nQuries; i++)
		{
			int l = in.nextInt() - 1;
			int r = in.nextInt() - 1;
			int x = in.nextInt();

			int result = -1;
			if (arr[l] != x)
				result = l+1;
			else if (next[l] <= r)
				result = next[l] + 1;
			ans.append(result + "\n");
		}

		// output
		System.out.print(ans.toString());
	}
}

class InputReader
{
	BufferedReader reader;
	StringTokenizer tok;

	public InputReader(InputStream stream)
	{
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tok = new StringTokenizer("");
	}

	public String next()
	{
		while (!tok.hasMoreTokens())
			try
			{
				tok = new StringTokenizer(reader.readLine());
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		return tok.nextToken();
	}
	
	public int nextInt()
	{
		return Integer.parseInt(next());
	}
}