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;
#pragma GCC optimize("-Ofast")
#pragma GCC optimize("trapv")
long long power(long long x, long long y) {
  if (y == 0) {
    return 1;
  }
  long long p = power(x, y / 2);
  p = (p * p);
  return (y % 2 == 0) ? p : (x * p);
}
long long powm(long long x, long long y, long long m) {
  long long ans = 1, r = 1;
  x %= m;
  while (r > 0 && r <= y) {
    if (r & y) {
      ans *= x;
      ans %= m;
    }
    r <<= 1;
    x *= x;
    x %= m;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
  long long lar = max(a, b);
  long long small = min(a, b);
  for (long long i = lar;; i += lar) {
    if (i % small == 0) {
      return i;
    }
  }
}
bool sortbysec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.second < b.second);
}
bool sortbydec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.first > b.first);
}
void dex(int a) {
  if (a == 1) {
    cout << "YES";
  }
  if (a == 2) {
    cout << "NO";
  }
  if (a == 3) {
    cout << "Yes";
  }
  if (a == 4) {
    cout << "No";
  }
}
void line(long long x) {
  for (long long i = 1; i <= x; i++) {
    cout << "-";
  }
  cout << '\n';
}
bool overflow(long double a, long double b) { return a * b > 1e18 + 10; }
long long mul(long long a, long long b, long long mod) {
  return ((a * 1LL * b) + mod) % mod;
}
long long sum(long long a, long long b, long long mod) { return (a + b) % mod; }
const long long N = (long long)(1e5 + 1);
const long long MOD = (long long)(1e9 + 7);
const long long INF = (long long)(2e18);
void solve(long long tc) {
  long long n, q;
  cin >> n >> q;
  long long a[n + 1];
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
  }
  long long b[n + 1];
  b[n] = -1;
  for (long long i = n - 1; i >= 1; i--) {
    if (a[i] != a[i + 1]) {
      b[i] = i + 1;
    } else {
      b[i] = b[i + 1];
    }
  }
  for (long long i = 1; i <= q; i++) {
    long long l, r, x;
    cin >> l >> r >> x;
    if (a[l] != x) {
      cout << l << '\n';
    } else if (b[l] <= r) {
      cout << b[l] << '\n';
    } else {
      cout << -1 << '\n';
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long cnt = 1;
  long long t = 1;
  while (t--) {
    for (auto blockTime = make_pair(chrono::high_resolution_clock::now(), true);
         blockTime.second;
         fprintf(stderr, "%s: %lld ms\n", "solve",
                 chrono::duration_cast<chrono::milliseconds>(
                     chrono::high_resolution_clock::now() - blockTime.first)
                     .count()),
              fflush(stderr), blockTime.second = false) {
      solve(cnt);
    }
    cnt++;
  }
  return 0;
}