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;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long int poww(long long int b, long long int e) {
  if (e == 0)
    return 1;
  else if (e % 2 == 0) {
    long long int a = pow(b, e / 2);
    return a * a;
  } else {
    long long int a = pow(b, e / 2);
    return b * a * a;
  }
}
long long int powm(long long int x, long long int y,
                   long long int m = 1000000007) {
  x = x % m;
  long long int res = 1;
  while (y) {
    if (y & 1) res = res * x;
    res %= m;
    y = y >> 1;
    x = x * x;
    x %= m;
  }
  return res;
}
long long int modInverse(long long int a, long long int m = 1000000007) {
  return powm(a, m - 2, m);
}
struct SegmentTree {
  long long int n;
  vector<vector<pair<long long int, long long int>>> v;
  SegmentTree(long long int size) {
    n = 4 * size + 1;
    v.resize(n);
  }
  void build(vector<long long int> ar, long long int ipos, long long int fpos,
             long long int pos = 1) {
    if (ipos > fpos) return;
    if (ipos == fpos)
      v[pos].push_back({ar[ipos], ipos});
    else {
      long long int mid = (ipos + fpos) / 2;
      build(ar, ipos, mid, pos * 2);
      build(ar, mid + 1, fpos, pos * 2 + 1);
      if (v[pos * 2].size() == 2)
        v[pos] = v[pos * 2];
      else if (v[pos * 2 + 1].size() == 2)
        v[pos] = v[pos * 2 + 1];
      else {
        vector<pair<long long int, long long int>> temp;
        temp.push_back(v[pos * 2][0]);
        if (v[pos * 2][0].first != v[pos * 2 + 1][0].first)
          temp.push_back(v[pos * 2 + 1][0]);
        v[pos] = temp;
      }
    }
  }
  vector<pair<long long int, long long int>> get_ans(long long int l,
                                                     long long int r,
                                                     long long int ipos,
                                                     long long int fpos,
                                                     long long int pos = 1) {
    vector<pair<long long int, long long int>> tt;
    long long int mid = (ipos + fpos) / 2;
    if ((l == ipos) && (r == fpos))
      return v[pos];
    else {
      vector<pair<long long int, long long int>> s1, s2;
      if ((ipos <= mid) && (l <= min(mid, r)))
        s1 = get_ans(l, min(mid, r), ipos, mid, pos * 2);
      if (((mid + 1) <= fpos) && ((max(mid + 1, l)) <= r))
        s2 = get_ans(max(mid + 1, l), r, mid + 1, fpos, pos * 2 + 1);
      if (s1.size() == 2)
        return s1;
      else if (s2.size() == 2)
        return s2;
      else {
        vector<pair<long long int, long long int>> temp;
        if (s2.size() == 0) return s1;
        if (s1.size() == 0) return s2;
        temp.push_back(s1[0]);
        if (s1[0].first != s2[0].first) temp.push_back(s2[0]);
        return temp;
      }
    }
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long int n, m;
  cin >> n >> m;
  vector<long long int> a(n);
  for (long long int i = (0); i <= (n - 1); i += (1)) cin >> a[i];
  ;
  long long int sl = -1, sli = -2, la = -1, lai = -2;
  vector<long long int> diff(n);
  for (long long int i = (0); i <= (n - 1); i += (1)) {
    if (a[i] != la) {
      diff[i] = lai;
      sl = la;
      sli = lai;
      la = a[i];
      lai = i;
    } else {
      diff[i] = sli;
      lai = i;
    }
  }
  while (m--) {
    long long int l, r, x;
    cin >> l >> r >> x;
    if (a[r - 1] != x)
      cout << r << "\n";
    else {
      if (diff[r - 1] + 1 < l)
        cout << -1 << "\n";
      else
        cout << (diff[r - 1] + 1) << "\n";
    }
  }
  return 0;
}