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;
class SparseTableRMQ {
 public:
  SparseTableRMQ(int *ar, int n) : n(n) {
    data = new int[n];
    for (int i = 0; i < n; ++i) data[i] = ar[i];
    table = buildRMQ();
  }
  ~SparseTableRMQ() {
    delete[] data;
    delete[] table;
  }
  int queryPos(int l, int r) {
    int k = lgInt(r - l - 1);
    int lid = table[l + n * k], rid = table[r + n * k - (1 << k)];
    return (data[lid] <= data[rid]) ? lid : rid;
  }
  int queryValue(int l, int r) { return data[queryPos(l, r)]; }

 private:
  int n, *table, *data;
  int lgInt(int v) {
    static const unsigned b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
    static const unsigned S[] = {1, 2, 4, 8, 16};
    int res = 0;
    for (int i = 4; i >= 0; i--) {
      if (v & b[i]) {
        v >>= S[i];
        res |= S[i];
      }
    }
    return res;
  }
  int *buildRMQ() {
    int logn = 1;
    for (int k = 1; k < n; k *= 2) ++logn;
    int *r = new int[n * logn];
    int *b = r;
    for (int i = 0; i < n; ++i) b[i] = i;
    for (int k = 1; k < n; k *= 2) {
      copy(b, b + n, b + n);
      b += n;
      for (int i = 0; i < n - k; ++i) {
        int idl = b[i], idr = b[i + k];
        if (data[idl] <= data[idr]) {
          b[i] = idl;
        } else {
          b[i] = idr;
        }
      }
    }
    return r;
  }
};
const int MX = 200099;
int N, M, A[MX], L[MX], R[MX], X[MX];
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < (int)N; ++i) scanf("%d", A + i);
  for (int i = 0; i < (int)M; ++i) scanf("%d%d%d", L + i, R + i, X + i);
  SparseTableRMQ rMinQ(A, N);
  for (int i = 0; i < (int)N; ++i) A[i] = -A[i];
  SparseTableRMQ rMaxQ(A, N);
  for (int i = 0; i < (int)N; ++i) A[i] = -A[i];
  for (int i = 0; i < (int)M; ++i) {
    --L[i];
    int minPos = rMinQ.queryPos(L[i], R[i]);
    int maxPos = rMaxQ.queryPos(L[i], R[i]);
    if (A[minPos] != X[i]) {
      printf("%d\n", minPos + 1);
    } else if (A[maxPos] != X[i]) {
      printf("%d\n", maxPos + 1);
    } else {
      printf("-1\n");
    }
  }
}