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 N = 200005;
struct Node {
  pair<int, int> mx, mn;
} node[4 * N];
int a[N];
void init(int i, int l, int r) {
  if (l > r) return;
  if (l == r) {
    node[i].mx = node[i].mn = make_pair(a[l], l);
    return;
  }
  int m = (l + r) >> 1;
  init(i << 1, l, m);
  init(i << 1 | 1, m + 1, r);
  node[i].mx = max(node[i << 1].mx, node[i << 1 | 1].mx);
  node[i].mn = min(node[i << 1].mn, node[i << 1 | 1].mn);
}
pair<int, int> get(int i, int l, int r, int a, int b, int type) {
  if (l > r || a > r || b < l)
    return (type == 1 ? make_pair(-0x3f3f3f3f, 0) : make_pair(0x3f3f3f3f, 0));
  if (a <= l && r <= b) return (type == 1 ? node[i].mx : node[i].mn);
  int m = (l + r) >> 1;
  return (type == 1 ? max(get(i << 1, l, m, a, b, type),
                          get(i << 1 | 1, m + 1, r, a, b, type))
                    : min(get(i << 1, l, m, a, b, type),
                          get(i << 1 | 1, m + 1, r, a, b, type)));
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  init(1, 1, n);
  while (m--) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    pair<int, int> res_mx = get(1, 1, n, l, r, 1);
    pair<int, int> res_mn = get(1, 1, n, l, r, 2);
    if (res_mx.first != x)
      printf("%d\n", res_mx.second);
    else if (res_mn.first != x)
      printf("%d\n", res_mn.second);
    else
      puts("-1");
  }
  return 0;
}