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;
const int MXN = 1e5 * 2 + 1;
const int TMXN = 1e5 * 8 + 1;
const int INF = 1e9 + 7;
const long long INFL = 1e18;
int n, m, l, r, res, c, mink, x;
int a[MXN], two = 1;
pair<int, int> zabei, zabei1;
pair<int, int> t[TMXN], d[TMXN];
inline void build(int v, int tl, int tr) {
  if (tl == tr)
    t[v].first = a[tl], t[v].second = tl, d[v].first = a[tl], d[v].second = tl;
  else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v].first = max(t[v * 2].first, t[v * 2 + 1].first);
    if (t[v * 2].first > t[v * 2 + 1].first) {
      t[v].second = t[v * 2].second;
    } else {
      t[v].second = t[v * 2 + 1].second;
    }
    d[v].first = min(d[v * 2].first, d[v * 2 + 1].first);
    if (d[v * 2].first < d[v * 2 + 1].first) {
      d[v].second = d[v * 2].second;
    } else {
      d[v].second = d[v * 2 + 1].second;
    }
  }
}
pair<int, int> combine(pair<int, int> c, pair<int, int> b) {
  if (c.first > b.first) {
    return c;
  } else {
    return b;
  }
}
pair<int, int> combine1(pair<int, int> c, pair<int, int> b) {
  if (c.first < b.first) {
    return c;
  } else {
    return b;
  }
}
pair<int, int> get(int v, int tl, int tr, int l, int r) {
  if (l > r) return zabei;
  if (l == tl && r == tr) return t[v];
  int tm = (tl + tr) / 2;
  return combine(get(v * 2, tl, tm, l, min(r, tm)),
                 get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
pair<int, int> getmin(int v, int tl, int tr, int l, int r) {
  if (l > r) return zabei1;
  if (l == tl && r == tr) return d[v];
  int tm = (tl + tr) / 2;
  return combine1(getmin(v * 2, tl, tm, l, min(r, tm)),
                  getmin(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}
int main() {
  ios_base::sync_with_stdio(0);
  scanf("%d%d", &n, &m);
  zabei.first = 0;
  zabei.second = 0;
  zabei1.first = INF;
  zabei.second = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &l, &r, &x);
    if (get(1, 1, n, l, r).first != x && get(1, 1, n, l, r).first != 0) {
      cout << get(1, 1, n, l, r).second << '\n';
      continue;
    }
    if (getmin(1, 1, n, l, r).first != x &&
        getmin(1, 1, n, l, r).first != INF) {
      cout << getmin(1, 1, n, l, r).second << '\n';
      continue;
    }
    cout << -1 << '\n';
  }
  return 0;
}