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 <class T>
inline T mod_v(T num) {
  if (num >= 0)
    return num % 1000000007;
  else
    return (num % 1000000007 + 1000000007) % 1000000007;
}
template <class T>
inline T gcd(T a, T b) {
  a = abs(a);
  b = abs(b);
  while (b) b ^= a ^= b ^= a %= b;
  return a;
}
template <class T>
T fast_pow(T n, T p) {
  if (p == 0) return 1;
  if (p % 2) {
    T g = mod_v(mod_v(n) * mod_v(fast_pow(n, p - 1)));
    return g;
  } else {
    T g = fast_pow(n, p / 2);
    g = mod_v(mod_v(g) * mod_v(g));
    return g;
  }
}
template <class T>
inline T modInverse(T n) {
  return fast_pow(n, 1000000007 - 2);
}
template <class T>
inline void debug(string S1, T S2, string S3) {
  cout << S1 << S2 << S3;
}
bool equalTo(double a, double b) {
  if (fabs(a - b) <= 1e-9)
    return true;
  else
    return false;
}
bool notEqual(double a, double b) {
  if (fabs(a - b) > 1e-9)
    return true;
  else
    return false;
}
bool lessThan(double a, double b) {
  if (a + 1e-9 < b)
    return true;
  else
    return false;
}
bool lessThanEqual(double a, double b) {
  if (a < b + 1e-9)
    return true;
  else
    return false;
}
bool greaterThan(double a, double b) {
  if (a > b + 1e-9)
    return true;
  else
    return false;
}
bool greaterThanEqual(double a, double b) {
  if (a + 1e-9 > b)
    return true;
  else
    return false;
}
template <class T>
inline int in(register T& num) {
  register char c = 0;
  num = 0;
  bool n = false;
  while (c < 33) c = getchar();
  while (c > 33) {
    if (c == '-')
      n = true;
    else
      num = num * 10 + c - '0';
    c = getchar();
  }
  num = n ? -num : num;
  return 1;
}
class nod {
 public:
  int x, y;
  int idx1, idx2;
};
nod tree[4 * 200005];
int kp[200005];
void build(int p, int l, int r) {
  if (l == r) {
    tree[p].x = tree[p].y = kp[l];
    tree[p].idx1 = tree[p].idx2 = l;
    return;
  }
  int mid = (l + r) >> 1;
  int left = p << 1;
  int right = left | 1;
  build(left, l, mid);
  build(right, mid + 1, r);
  if (tree[left].x != tree[left].y)
    tree[p] = tree[left];
  else if (tree[right].x != tree[right].y)
    tree[p] = tree[right];
  else {
    if (tree[left].x != tree[right].x) {
      tree[p].x = tree[left].x;
      tree[p].idx1 = tree[left].idx1;
      tree[p].y = tree[right].x;
      tree[p].idx2 = tree[right].idx1;
    } else if (tree[left].x != tree[right].y) {
      tree[p].x = tree[left].x;
      tree[p].idx1 = tree[left].idx1;
      tree[p].y = tree[right].y;
      tree[p].idx2 = tree[right].idx2;
    } else if (tree[left].y != tree[right].x) {
      tree[p].x = tree[left].y;
      tree[p].idx1 = tree[left].idx2;
      tree[p].y = tree[right].x;
      tree[p].idx2 = tree[right].idx1;
    } else if (tree[left].y != tree[right].y) {
      tree[p].x = tree[left].y;
      tree[p].idx1 = tree[left].idx2;
      tree[p].y = tree[right].y;
      tree[p].idx2 = tree[right].idx2;
    } else
      tree[p] = tree[left];
  }
}
int u, v, idx, x;
void qu(int p, int l, int r) {
  if (v < l || u > r) return;
  if (idx != -1) return;
  if (u <= l && r <= v) {
    if (tree[p].x != x)
      idx = tree[p].idx1;
    else if (tree[p].y != x)
      idx = tree[p].idx2;
    return;
  }
  int mid = (l + r) >> 1;
  int left = p << 1;
  int right = left | 1;
  qu(left, l, mid);
  qu(right, mid + 1, r);
}
int main() {
  int n, m;
  in(n), in(m);
  for (int i = 1; i <= n; i++) in(kp[i]);
  build(1, 1, n);
  while (m--) {
    in(u), in(v), in(x);
    idx = -1;
    qu(1, 1, n);
    printf("%d\n", idx);
  }
  return 0;
}