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 maxn = 200500;
int n, m, a[maxn], mx[maxn << 2], mi[maxn << 2], e;
vector<int> vec[1000200];
map<int, int> mp;
void PushUP(int rt) {
  mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
  mi[rt] = min(mi[rt << 1], mi[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
  if (l == r) {
    scanf("%d", &mi[rt]);
    mx[rt] = mi[rt];
    vec[mi[rt]].push_back(++e);
    mp[mi[rt]];
    return;
  }
  int m = (l + r) / 2;
  build(l, m, rt << 1), build(m + 1, r, rt << 1 | 1);
  PushUP(rt);
}
int query_mx(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return mx[rt];
  }
  int m = (l + r) / 2, ret = -1;
  if (L <= m) ret = max(ret, query_mx(L, R, l, m, rt << 1));
  if (m < R) ret = max(ret, query_mx(L, R, m + 1, r, rt << 1 | 1));
  return ret;
}
int query_mi(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return mi[rt];
  }
  int m = (l + r) / 2, ret = 2000000;
  if (L <= m) ret = min(ret, query_mi(L, R, l, m, rt << 1));
  if (m < R) ret = min(ret, query_mi(L, R, m + 1, r, rt << 1 | 1));
  return ret;
}
int main() {
  while (scanf("%d%d", &n, &m) != EOF) {
    mp.clear();
    e = 0;
    for (int i = 1; i <= 1000100; i++) vec[i].clear();
    build(1, n, 1);
    while (m--) {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      if (mp.find(k) == mp.end()) {
        printf("%d\n", l);
        continue;
      }
      int MI = query_mi(l, r, 1, n, 1);
      int MX = query_mx(l, r, 1, n, 1);
      if (MI == k && MX == k)
        puts("-1");
      else {
        if (MI != k)
          k = MI;
        else
          k = MX;
        vector<int>::iterator it = lower_bound(vec[k].begin(), vec[k].end(), r);
        int idx = it - vec[k].begin();
        if (idx == vec[k].size() || vec[k][idx] > r) idx--;
        printf("%d\n", vec[k][idx]);
      }
    }
  }
}