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 <int POS, class TUPLE>
void deploy(std::ostream &os, const TUPLE &tuple) {}
template <int POS, class TUPLE, class H, class... Ts>
void deploy(std::ostream &os, const TUPLE &t) {
  os << (POS == 0 ? "" : ", ") << get<POS>(t);
  deploy<POS + 1, TUPLE, Ts...>(os, t);
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> &p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::vector<T> &v) {
  int remain = v.size();
  os << "{";
  for (auto e : v) os << e << (--remain == 0 ? "}" : ", ");
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::set<T> &v) {
  int remain = v.size();
  os << "{";
  for (auto e : v) os << e << (--remain == 0 ? "}" : ", ");
  return os;
}
template <class T, class K>
std::ostream &operator<<(std::ostream &os, std::map<T, K> &make_pair) {
  int remain = make_pair.size();
  os << "{";
  for (auto e : make_pair)
    os << "(" << e.first << " -> " << e.second << ")"
       << (--remain == 0 ? "}" : ", ");
  return os;
}
using ll = long long;
template <typename val_t = int>
struct NodeMIN {
  val_t x;
  int id;
  NodeMIN() {
    x = INT_MAX;
    id = 0;
  }
  NodeMIN(val_t x_, int id_) {
    x = x_;
    id = id_;
  }
};
template <int NV>
class SegTreeMIN {
  int n;
  vector<NodeMIN<> > seg_tree;
  inline NodeMIN<> MAXNODE() {
    return NodeMIN<>(std::numeric_limits<decltype(NodeMIN<>().x)>::max(), -1);
  }
  inline NodeMIN<> comp(NodeMIN<> &a, NodeMIN<> &b) {
    if (a.x <= b.x) {
      return a;
    } else {
      return b;
    }
  }

 public:
  SegTreeMIN() { seg_tree.resize(NV * 2, NodeMIN<>()); }
  void init(int n_) {
    n = 1;
    while (n < n_) {
      n *= 2;
    }
  }
  inline NodeMIN<> query(int a, int b) { return query(a, b, 0, 0, n); }
  inline void update(int k, NodeMIN<> &a) {
    k += n - 1;
    seg_tree[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      seg_tree[k] = comp(seg_tree[k * 2 + 1], seg_tree[k * 2 + 2]);
    }
  }
  inline NodeMIN<> query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) {
      return MAXNODE();
    }
    if (a <= l && r <= b) {
      return seg_tree[k];
    }
    NodeMIN<> vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    NodeMIN<> vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return comp(vl, vr);
  }
};
template <typename val_t = int>
struct NodeMAX {
  val_t x;
  int id;
  NodeMAX() {
    x = -1;
    id = 0;
  }
  NodeMAX(int x_, int id_) {
    x = x_;
    id = id_;
  }
};
template <int NV>
class SegTreeMAX {
  int n;
  vector<NodeMAX<> > seg_tree;
  inline NodeMAX<> MINNODE() { return NodeMAX<>(-1, -1); }
  inline NodeMAX<> comp(NodeMAX<> &a, NodeMAX<> &b) {
    if (a.x <= b.x) {
      return b;
    } else {
      return a;
    }
  }

 public:
  SegTreeMAX() { seg_tree.resize(NV * 2, NodeMAX<>()); }
  void init(int n_) {
    n = 1;
    while (n < n_) {
      n *= 2;
    }
  }
  inline NodeMAX<> query(int a, int b) { return query(a, b, 0, 0, n); }
  inline void update(int k, NodeMAX<> &a) {
    k += n - 1;
    seg_tree[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      seg_tree[k] = comp(seg_tree[k * 2 + 1], seg_tree[k * 2 + 2]);
    }
  }
  inline NodeMAX<> query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) {
      return MINNODE();
    }
    if (a <= l && r <= b) {
      return seg_tree[k];
    }
    NodeMAX<> vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    NodeMAX<> vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return comp(vl, vr);
  }
};
SegTreeMAX<400100> STMAX;
SegTreeMIN<400100> STMIN;
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  int N, M;
  cin >> N >> M;
  STMAX.init(N + 4);
  STMIN.init(N + 4);
  for (int i = 0; i < (N); i++) {
    int x;
    cin >> x;
    auto nmax = NodeMAX<>(x, i);
    auto nmin = NodeMIN<>(x, i);
    STMAX.update(i, nmax);
    STMIN.update(i, nmin);
  }
  for (int i = 0; i < (M); i++) {
    int l, r, x;
    cin >> l >> r >> x;
    l--;
    auto nmax = STMAX.query(l, r);
    auto nmin = STMIN.query(l, r);
    if (nmax.x != x) {
      cout << nmax.id + 1 << "\n";
    } else if (nmin.x != x) {
      cout << nmin.id + 1 << "\n";
    } else {
      cout << -1 << "\n";
    }
  }
  return 0;
}