3 2
1 0 1
1 2
2 3
 10 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
6 7
8 3
6 4
4 2
9 2
5 10
9 8
10 7
5 1
6 2

2
1
2
 0

#include <bits/stdc++.h>
using namespace std;
mt19937_64 randgen;
long long rng_seed = 0;
void set_seed(long long seed) {
  randgen.seed(seed);
  rng_seed = seed;
}
long long RNG() {
  rng_seed = rng_seed * 0x19267 ^ (rng_seed >> 23);
  return rng_seed;
}
long long getrand(long long a, long long b) {
  long long v = 1;
  while (v < b - a + 5) {
    v <<= 1;
  }
  while (true) {
    int ind = RNG() & (v - 1);
    if (ind + a <= b) {
      return ind + a;
    }
  }
}
template <typename T>
void read_to_vector(size_t N, std::vector<T> &v) {
  for (size_t i = 0; i < N; i++) {
    T tmp;
    std::cin >> tmp;
    v.push_back(tmp);
  }
}
template <typename T>
void print_vector(const std::vector<T> &v) {
  for (auto it = v.begin(); it < v.end(); it++) {
    if (it != v.begin()) std::cout << " ";
    std::cout << (*it);
  }
}
vector<long long> a;
vector<vector<long long> > inds;
long long direct(long long l, long long r, long long k) {
  map<long long, long long> counts;
  for (int i = l; i <= r; i++) {
    counts[a[i]]++;
  }
  for (auto p : counts) {
    if (p.second * k > r - l + 1) {
      return p.first;
    }
  }
  return -1;
}
const long long NSAMPLE = 80;
const long long NREQ = 1;
long long binary(const vector<long long> &vec, long long x, long long a = 0) {
  long long N = vec.size();
  long long b = N;
  while (a < b) {
    long long c = (a + b) / 2;
    if (vec[c] < x) {
      a = c + 1;
    } else {
      b = c;
    }
  }
  return b;
}
long long count(long long x, long long l, long long r, long long mincount = 0) {
  if (inds[x].size() < mincount) {
    return 0;
  }
  long long start = binary(inds[x], l);
  long long end = binary(inds[x], r + 1, l);
  return end - start;
}
long long sample(long long l, long long r, long long k) {
  static vector<long long> nums(NSAMPLE, 0);
  for (int i = 0; i < NSAMPLE; i++) {
    int ind = getrand(l, r);
    nums[i] = a[ind];
  }
  sort(nums.begin(), nums.end());
  for (int i = 0; i < NSAMPLE - NREQ + 1; i++) {
    long long x = nums[i];
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue;
    }
    if (nums[i + NREQ - 1] != nums[i]) {
      continue;
    }
    long long c = count(x, l, r, (r - l + 1) / k + 1);
    if (c * k > r - l + 1) {
      return x;
    }
  }
  return -1;
}
void solve() {
  long long seed = 0;
  long long n, q;
  cin >> n >> q;
  seed += n + q;
  read_to_vector(n, a);
  inds = vector<vector<long long> >(n + 1, vector<long long>());
  for (int i = 0; i < n; i++) {
    seed += a[i];
    inds[a[i]].push_back(i);
  }
  set_seed(seed);
  for (int i = 0; i < q; i++) {
    long long l, r, k;
    cin >> l >> r >> k;
    if (r - l < 00) {
      cout << direct(l - 1, r - 1, k) << "\n";
    } else {
      cout << sample(l - 1, r - 1, k) << "\n";
    }
  }
}
void pre_compute() {}
int main() {
  std::cout << std::setprecision(15);
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  pre_compute();
  solve();
  return 0;
}
