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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int N, A[200005], men[200005][40], may[200005][40], Q, a, b, x;
pair<int, int> query(int a, int b) {
  int menor, mayor;
  if (b < a) swap(a, b);
  int l = log2(b - a + 1);
  if (A[men[a][l]] < A[men[b - (1 << l) + 1][l]])
    menor = men[a][l];
  else
    menor = men[b - (1 << l) + 1][l];
  if (A[may[a][l]] > A[may[b - (1 << l) + 1][l]])
    mayor = may[a][l];
  else
    mayor = may[b - (1 << l) + 1][l];
  return pair<int, int>(menor, mayor);
}
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin >> N >> Q;
  for (int i = 1; i <= N; i++) cin >> A[i], men[i][0] = i, may[i][0] = i;
  for (int i = 1; (1 << i) <= N; i++)
    for (int j = 1; j + (1 << i) - 1 <= N; j++) {
      int l1 = men[j][i - 1];
      int r1 = men[j + (1 << (i - 1))][i - 1];
      if (A[l1] < A[r1])
        men[j][i] = l1;
      else
        men[j][i] = r1;
      l1 = may[j][i - 1];
      r1 = may[j + (1 << (i - 1))][i - 1];
      if (A[l1] > A[r1])
        may[j][i] = l1;
      else
        may[j][i] = r1;
    }
  while (Q--) {
    cin >> a >> b >> x;
    auto v = query(a, b);
    if (A[v.first] != x)
      cout << v.first << "\n";
    else if (A[v.second] != x)
      cout << v.second << "\n";
    else
      cout << "-1\n";
  }
}