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>
const int64_t kMaxSize = static_cast<int64_t>(3e7);
void task_a() {
  int64_t num = 0;
  std::cin >> num;
  std::vector<int64_t> triangles(kMaxSize);
  for (int64_t i = 0; i < kMaxSize; ++i) {
    triangles[i] = i * (i + 1) / 2;
  }
  int pointer = 0;
  while (triangles[pointer] < num) {
    pointer += 1;
  }
  pointer -= 1;
  std::cout << num - triangles[pointer] << std::endl;
}
void task_b() {
  int h = 0, m = 0;
  scanf("%d:%d", &h, &m);
  int add = 0;
  scanf("%d", &add);
  int time = 60 * h + m + add;
  printf("%02d:%02d\n", (time / 60) % 24, time % 60);
}
void task_c() {
  std::ios_base::sync_with_stdio(false);
  int n = 0, m = 0;
  std::cin >> n >> m;
  std::vector<int> nums(n);
  std::vector<int> rightmost_not_equal(n);
  rightmost_not_equal[0] = -1;
  for (int i = 0; i < n; ++i) {
    std::cin >> nums[i];
    if (i > 0) {
      rightmost_not_equal[i] =
          (nums[i] == nums[i - 1]) ? rightmost_not_equal[i - 1] : i - 1;
    }
  }
  for (int i = 0; i < m; ++i) {
    int left = 0, right = 0, x = 0;
    std::cin >> left >> right >> x;
    left -= 1;
    right -= 1;
    if (nums[right] == x && (rightmost_not_equal[right] == -1 ||
                             rightmost_not_equal[right] < left)) {
      std::cout << -1 << std::endl;
    } else if (nums[right] != x) {
      std::cout << right + 1 << std::endl;
    } else {
      std::cout << rightmost_not_equal[right] + 1 << std::endl;
    }
  }
}
int main() {
  task_c();
  return 0;
}