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 = 200005;
int a[maxn];
struct node {
  int l, r, Max, Min, pa, pi;
} T[maxn << 2];
void pushup(int o) {
  T[o].Min = min(T[o << 1].Min, T[o << 1 | 1].Min);
  T[o].Max = max(T[o << 1].Max, T[o << 1 | 1].Max);
  if (T[o].Min == T[o << 1].Min)
    T[o].pi = T[o << 1].pi;
  else
    T[o].pi = T[o << 1 | 1].pi;
  if (T[o].Max == T[o << 1].Max)
    T[o].pa = T[o << 1].pa;
  else
    T[o].pa = T[o << 1 | 1].pa;
}
void build(int o, int l, int r) {
  T[o].l = l;
  T[o].r = r;
  if (l == r) {
    T[o].Max = T[o].Min = a[l];
    T[o].pa = T[o].pi = l;
    return;
  }
  int mid = (l + r) >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  pushup(o);
}
int query(int o, int l, int r, int op) {
  if (T[o].l == l && T[o].r == r) {
    if (op == 1)
      return T[o].Max;
    else if (op == 2)
      return T[o].Min;
    else if (op == 3)
      return T[o].pa;
    else
      return T[o].pi;
  }
  int mid = (T[o].l + T[o].r) >> 1;
  if (r <= mid)
    return query(o << 1, l, r, op);
  else if (l > mid)
    return query(o << 1 | 1, l, r, op);
  else {
    if (op == 1)
      return max(query(o << 1, l, mid, 1), query(o << 1 | 1, mid + 1, r, 1));
    else if (op == 2)
      return min(query(o << 1, l, mid, 2), query(o << 1 | 1, mid + 1, r, 2));
    else if (op == 3) {
      int ans1 = query(o << 1, l, mid, 1),
          ans2 = query(o << 1 | 1, mid + 1, r, 1);
      int ans = max(ans1, ans2);
      if (ans == ans1)
        return query(o << 1, l, mid, 3);
      else
        return query(o << 1 | 1, mid + 1, r, 3);
    } else {
      int ans1 = query(o << 1, l, mid, 2),
          ans2 = query(o << 1 | 1, mid + 1, r, 2);
      int ans = min(ans1, ans2);
      if (ans == ans1)
        return query(o << 1, l, mid, 4);
      else
        return query(o << 1 | 1, mid + 1, r, 4);
    }
  }
}
int main() {
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    build(1, 1, n);
    int l, r, x, Max, Min, pa, pi;
    while (m--) {
      scanf("%d%d%d", &l, &r, &x);
      Max = query(1, l, r, 1);
      Min = query(1, l, r, 2);
      pa = query(1, l, r, 3);
      pi = query(1, l, r, 4);
      int ans;
      if (Max == Min && Max == x)
        ans = -1;
      else if (Min != x)
        ans = pi;
      else if (Max != x)
        ans = pa;
      printf("%d\n", ans);
    }
  }
  return 0;
}