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;
const int maxn = 2e5 + 500;
int n, m, s[maxn];
struct Node {
  int left, right, mxid, mnid;
} node[maxn * 8];
void pushUP(int i) {
  if (s[node[i * 2].mxid] >= s[node[i * 2 + 1].mxid])
    node[i].mxid = node[i * 2].mxid;
  else
    node[i].mxid = node[i * 2 + 1].mxid;
  if (s[node[i * 2].mnid] <= s[node[i * 2 + 1].mnid])
    node[i].mnid = node[i * 2].mnid;
  else
    node[i].mnid = node[i * 2 + 1].mnid;
}
void BuildTree(int i, int l, int r) {
  node[i].left = l;
  node[i].right = r;
  if (l == r) {
    int x;
    node[i].mnid = node[i].mxid = l;
    return;
  }
  int m = (l + r) / 2;
  BuildTree(i * 2, l, m);
  BuildTree(i * 2 + 1, m + 1, r);
  pushUP(i);
}
int querymx(int i, int l, int r) {
  if (node[i].left == l && node[i].right == r) {
    return node[i].mxid;
  }
  int lid = 0, rid = 0;
  if (l <= node[i * 2].right) {
    if (r <= node[i * 2].right)
      lid = querymx(i * 2, l, r);
    else
      lid = querymx(i * 2, l, node[i * 2].right);
  }
  if (r >= node[i * 2 + 1].left) {
    if (l >= node[i * 2 + 1].left)
      rid = querymx(i * 2 + 1, l, r);
    else
      rid = querymx(i * 2 + 1, node[i * 2 + 1].left, r);
  }
  if (s[lid] > s[rid])
    return lid;
  else
    return rid;
}
int querymn(int i, int l, int r) {
  if (node[i].left == l && node[i].right == r) {
    return node[i].mnid;
  }
  int lid = 0, rid = 0;
  if (l <= node[i * 2].right) {
    if (r <= node[i * 2].right)
      lid = querymn(i * 2, l, r);
    else
      lid = querymn(i * 2, l, node[i * 2].right);
  }
  if (r >= node[i * 2 + 1].left) {
    if (l >= node[i * 2 + 1].left)
      rid = querymn(i * 2 + 1, l, r);
    else
      rid = querymn(i * 2 + 1, node[i * 2 + 1].left, r);
  }
  if (s[lid] < s[rid])
    return lid;
  else
    return rid;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
  BuildTree(1, 1, n);
  int l, r, x, mx, mn;
  while (m--) {
    scanf("%d%d%d", &l, &r, &x);
    s[0] = -1;
    mx = querymx(1, l, r);
    s[0] = 1e6 + 9;
    mn = querymn(1, l, r);
    if (s[mx] != x)
      printf("%d\n", mx);
    else if (s[mn] != x)
      printf("%d\n", mn);
    else
      printf("-1\n");
  }
  return 0;
}