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 std::abs;
using std::cerr;
using std::cin;
using std::cout;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::pair;
using std::set;
using std::string;
using std::vector;
template <typename T>
T input() {
  T res;
  cin >> res;
  return res;
}
struct query {
  uint32_t l;
  uint32_t r;
  uint32_t x;
  uint32_t ans;
};
int main() {
  std::iostream::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<uint32_t> arr(input<uint32_t>());
  vector<query> queries(input<uint32_t>());
  vector<uint32_t> order(queries.size());
  std::generate(arr.begin(), arr.end(), input<uint32_t>);
  for (uint32_t i = 0; i != queries.size(); ++i) {
    auto& q = queries[i];
    cin >> q.l >> q.r >> q.x;
    --q.l, --q.r, q.ans = UINT32_MAX;
    order[i] = i;
  }
  std::sort(order.begin(), order.end(), [&queries](uint32_t a, uint32_t b) {
    return queries[a].l < queries[b].l;
  });
  std::map<uint32_t, vector<uint32_t>> cur_queries;
  uint32_t ptr = 0;
  for (uint32_t i = 0; i != arr.size(); ++i) {
    while (ptr != order.size() and queries[order[ptr]].l == i)
      cur_queries[queries[order[ptr]].x].push_back(order[ptr]), ++ptr;
    for (auto& dat : cur_queries)
      if (dat.first != arr[i]) {
        for (uint32_t v : dat.second)
          if (queries[v].r >= i) queries[v].ans = i;
        dat.second.clear(), dat.second.shrink_to_fit();
      }
    auto it = cur_queries.find(arr[i]);
    cur_queries.erase(cur_queries.begin(), it);
    if (it != cur_queries.end()) ++it;
    cur_queries.erase(it, cur_queries.end());
  }
  for (auto q : queries) {
    if (q.ans == UINT32_MAX)
      cout << "-1\n";
    else
      cout << q.ans + 1 << "\n";
  }
  return 0;
}