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 long long mod = 1e9 + 7;
const int N = 2e5 + 5;
const int M = 1e6 + 5;
int a[N];
vector<int> pos[M];
int MAX[N << 2], MIN[N << 2];
void PushUp(int rt) {
  MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
  MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
  if (l == r) {
    MAX[rt] = MIN[rt] = a[l];
    return;
  }
  int m = (l + r) >> 1;
  build(l, m, rt << 1);
  build(m + 1, r, rt << 1 | 1);
  PushUp(rt);
}
int query1(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) return MAX[rt];
  int m = (l + r) >> 1;
  int ret = -1e9;
  if (L <= m) ret = max(ret, query1(L, R, l, m, rt << 1));
  if (m < R) ret = max(ret, query1(L, R, m + 1, r, rt << 1 | 1));
  return ret;
}
int query2(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) return MIN[rt];
  int m = (l + r) >> 1;
  int ret = 1e9;
  if (L <= m) ret = min(ret, query2(L, R, l, m, rt << 1));
  if (m < R) ret = min(ret, query2(L, R, m + 1, r, rt << 1 | 1));
  return ret;
}
int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 1; i <= M - 1; i++) pos[i].clear();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), pos[a[i]].push_back(i);
    build(1, n, 1);
    for (int i = 1; i <= m; i++) {
      int l, r, x;
      scanf("%d%d%d", &l, &r, &x);
      int ma = query1(l, r, 1, n, 1), mi = query2(l, r, 1, n, 1);
      if (ma == x && mi == x) {
        printf("-1\n");
        continue;
      }
      if (ma > x) {
        int loc =
            lower_bound(pos[ma].begin(), pos[ma].end(), l) - pos[ma].begin();
        printf("%d\n", pos[ma][loc]);
      } else {
        int loc =
            lower_bound(pos[mi].begin(), pos[mi].end(), l) - pos[mi].begin();
        printf("%d\n", pos[mi][loc]);
      }
    }
  }
  return 0;
}