#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <experimental/random>

class EmptyList { };
class EmptyDict { };

template <class T, class S>
struct CommonType { };

struct String;

template <class T>
struct List {
    std::shared_ptr<std::vector<T>> inner;

    List() : inner(std::shared_ptr<std::vector<T>>(new std::vector<T>())) {}
    List(std::vector<T> a) : inner(std::shared_ptr<std::vector<T>>(new std::vector<T>(a))) {}
    template <class S>
    List(List<S> a) : inner(std::shared_ptr<std::vector<T>>(new std::vector<T>(a.inner->begin(), a.inner->end()))) {}
    List(EmptyList) : inner(std::shared_ptr<std::vector<T>>(new std::vector<T>())) {}
    T &operator[](size_t index) { return (*inner)[index]; }
    const T &operator[](size_t index) const { return (*inner)[index]; }
    void push(T value) { inner->push_back(value); }
    void pop() { inner->pop_back(); }
    int64_t length() const { return inner->size(); }

    template <class SortFn>
    void sort(SortFn sortFn) { std::sort(inner->begin(), inner->end(), sortFn); }

    template <class S>
    List<typename CommonType<T, S>::inner> concat(List<S> other) { List<typename CommonType<T, S>::inner> ret = EmptyList(); ret.inner->insert(ret.inner->end(), inner->begin(), inner->end()); ret.inner->insert(ret.inner->end(), other.inner->begin(), other.inner->end()); return ret; }
    String join(String delim);
};

struct String {
    std::shared_ptr<std::string> inner;

    String() : inner(std::shared_ptr<std::string>(new std::string())) {}
    String(const char* a) : inner(std::shared_ptr<std::string>(new std::string(a))) {}
    String(std::string a) : inner(std::shared_ptr<std::string>(new std::string(a))) {}
    String operator +(String other) { return String(*inner + *other.inner); }
    operator std::string() { return *inner; }
    String operator[](size_t index) const { return String(std::string({(*inner)[index]})); }
    int64_t charCodeAt(size_t index) const { return (*inner)[index]; }
    String operator+(String &other) const { return String(*inner + *other.inner); }
    String& operator+=(const String &other) { *inner += *other.inner; return *this; }
    char operator <(const String &other) const { return *inner < *other.inner; }
    char operator >(const String &other) const { return *inner > *other.inner; }
    char operator <=(const String &other) const { return *inner <= *other.inner; }
    char operator >=(const String &other) const { return *inner >= *other.inner; }
    char operator ==(const String &other) const { return *inner == *other.inner; }
    char operator !=(const String &other) const { return *inner != *other.inner; }
    int64_t length() const { return inner->size(); }

    String trim() {
        std::string s = *inner;
        const char* ws = " \t\n\r\f\v";
        s.erase(s.find_last_not_of(ws) + 1);
        s.erase(0, s.find_first_not_of(ws));
        return String(s);
    }
    List<String> split(String delim) { std::vector<String> ret; size_t last = 0; size_t next = 0; while ((next = inner->find(*delim.inner, last)) != std::string::npos) {   ret.push_back(String(inner->substr(last, next-last)));   last = next + delim.length(); } ret.push_back(String(inner->substr(last))); return ret; }
};

template<> String List<String>::join(String delim) {
    std::string ret; bool first = true; for (const auto& it: *inner) { if (!first) ret += *delim.inner; first = false; ret += *it.inner; } return ret;
}

template <class K, class V> 
struct Dict {
    using Inner = __gnu_pbds::tree<K, V, std::less<K>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
    std::shared_ptr<Inner> inner;

    Dict() : inner(std::shared_ptr<Inner>(new Inner())) {}
    Dict(std::vector<std::pair<K, V>> a) : inner(std::shared_ptr<Inner>(new Inner(a.begin(), a.end()))) {}
    template <class K2, class V2>
    Dict(Dict<K2, V2> a) : inner(std::shared_ptr<Inner>(new Inner(a.inner->begin(), a.inner->end()))) {}
    Dict(EmptyDict) : inner(std::shared_ptr<Inner>(new Inner())) {}
    V &operator[](K key) { return (*inner)[key]; }
    const V &operator[](K key) const { return (*inner)[key]; }
    int64_t length() const { return inner->size(); }
    bool contains(const K& k) const { return inner->find(k) != inner->end(); }
    void remove(const K& k) const { inner->erase(k); }
    K keyAt(int64_t pos) const { return inner->find_by_order(pos)->first; }
    int64_t bisect(const K& value) const { return inner->order_of_key(value); }

    List<K> keys() const { std::vector<K> ret; for (auto const& it: *inner) { ret.push_back(it.first); }; return List<K>(ret); }
};

template <class T> struct CommonType<List<T>, EmptyList> { using inner = List<T>; };
template <class T> struct CommonType<EmptyList, List<T>> { using inner = List<T>; };
template <class T, class S> struct CommonType<List<T>, List<S>> { using inner = List<typename CommonType<T, S>::inner>; };

template <class T> struct CommonType<std::nullptr_t, std::shared_ptr<T>> { using inner = std::shared_ptr<T>; };
template <class T> struct CommonType<std::shared_ptr<T>, std::nullptr_t> { using inner = std::shared_ptr<T>; };

template <class K, class V> struct CommonType<Dict<K, V>, EmptyDict> { using inner = Dict<K, V>; };
template <class K, class V> struct CommonType<EmptyDict, Dict<K, V>> { using inner = Dict<K, V>; };
template <class K, class V, class K2, class V2> struct CommonType<Dict<K, V>, Dict<K2, V2>> { using inner = Dict<typename CommonType<K, K2>::inner, typename CommonType<V, V2>::inner>; };

template <> struct CommonType<int64_t, int64_t> { using inner = int64_t; };
template <> struct CommonType<EmptyList, EmptyList> { using inner = EmptyList; };
template <> struct CommonType<EmptyDict, EmptyDict> { using inner = EmptyDict; };
template <> struct CommonType<std::nullptr_t, std::nullptr_t> { using inner = std::nullptr_t; };
template <> struct CommonType<char, char> { using inner = char; };
template <> struct CommonType<String, String> { using inner = String; };

int64_t cast_int(long int x) { return x; }
int64_t cast_int(long long int x) { return x; }
int64_t cast_int(double x) { return x; }
int64_t cast_int(String x) { return std::strtoll(x.inner->c_str(), NULL, 10); }

double cast_float(long int x) { return x; }
double cast_float(long long int x) { return x; }
double cast_float(double x) { return x; }
double cast_float(String x) { return std::strtod(x.inner->c_str(), NULL); }

String cast_str(long int x) { return String(std::to_string(x)); }
String cast_str(long long int x) { return String(std::to_string(x)); }
String cast_str(double x) { return String(std::to_string(x)); }
String cast_str(bool x) { return String(std::to_string(x)); }
String cast_str(String x) { return x; }

bool rand_bool() { return rand() % 100 < 50; }
int64_t rand_int(int64_t upper) { return std::experimental::randint(int64_t(0), upper); }
String chr(int64_t x) { return String(std::string({(char)x})); }

template <class T>
struct TypeHolder { };

template <class T, class S, class Filter, class Mapper>
List<T> linq(const List<S> &input, Filter filter, Mapper mapper, TypeHolder<T> type_holder) {
    List<T> ret;
    for (const auto &it: *input.inner) {
        if (filter(it)) {
            ret.push(mapper(it));
        }
    }
    return ret;
}

struct Node;
char Node$less(std::shared_ptr<Node> self, std::shared_ptr<Node> other);
int64_t get(int64_t l, int64_t r, int64_t k, List<int64_t> u, List<int64_t> a);
String solve(String input);
struct Node{int64_t l;int64_t r;int64_t k;int64_t ind;};
bool operator < (std::shared_ptr<Node> self, std::shared_ptr<Node> other) {
if (((self->l/317ll)==(other->l/317ll))) {
return (self->r<other->r);
}
return ((self->l/317ll)<(other->l/317ll));
}
char Node$less(std::shared_ptr<Node> self, std::shared_ptr<Node> other) {
if (((self->l/317ll)==(other->l/317ll))) {
return (self->r<other->r);
}
return ((self->l/317ll)<(other->l/317ll));
}
int64_t get(int64_t l, int64_t r, int64_t k, List<int64_t> u, List<int64_t> a) {
int64_t mn = ((int64_t)((a).length())+1ll);
for (int64_t i = 0ll; (i<100ll); i+=1ll) {
int64_t nw = (a)[(l+((rand_int)((int64_t)((a).length()))%(((r-l)+1ll))))];
if ((((u)[nw]>((((r-l)+1ll))/k))&&(nw<mn))) {
mn = nw;
}

}
if ((mn==((int64_t)((a).length())+1ll))) {
mn = - 1ll;
}
return mn;
}
String solve(String input) {
List<String> lines = (input).split(String("\n"));
List<int64_t> vls = linq(((lines)[0ll]).split(String(" ")), [=](String x) { return true;  }, [=](String x) { return cast_int(x); }, TypeHolder<int64_t>());
int64_t n = (vls)[0ll];
int64_t q = (vls)[1ll];
List<int64_t> a = linq(((lines)[1ll]).split(String(" ")), [=](String x) { return true;  }, [=](String x) { return cast_int(x); }, TypeHolder<int64_t>());
List<int64_t> u = EmptyList();
for (int64_t i = 0ll; (i<=n); i+=1ll) {
(u).push(0ll);

}
List<int64_t> anss = EmptyList();
List<std::shared_ptr<Node>> qu = EmptyList();
for (int64_t i = 2ll; (i<=(1ll+q)); i+=1ll) {
List<int64_t> cr = linq(((lines)[i]).split(String(" ")), [=](String x) { return true;  }, [=](String x) { return cast_int(x); }, TypeHolder<int64_t>());
int64_t l = (cr)[0ll];
int64_t r = (cr)[1ll];
int64_t k = (cr)[2ll];
(qu).push(std::shared_ptr<Node>(new Node{(l-1ll),(r-1ll),k,(i-2ll)}));

}
(qu).sort([](std::shared_ptr<Node> a, std::shared_ptr<Node> b) { return Node$less(a,  b); });
for (int64_t i = (qu)[0ll]->l; (i<=(qu)[0ll]->r); i+=1ll) {
(u)[(a)[i]]+=1ll;

}
List<int64_t> ans = EmptyList();
for (int64_t i = 0ll; (i<q); i+=1ll) {
(ans).push(- 1ll);

}
(ans)[(qu)[0ll]->ind] = (get)((qu)[0ll]->l, (qu)[0ll]->r, (qu)[0ll]->k, u, a);
for (int64_t iq = 1ll; (iq<q); iq+=1ll) {
int64_t prl = (qu)[(iq-1ll)]->l;
int64_t prr = (qu)[(iq-1ll)]->r;
int64_t l = (qu)[iq]->l;
int64_t r = (qu)[iq]->r;
int64_t ind = (qu)[iq]->ind;
int64_t k = (qu)[iq]->k;
for (int64_t i = prl; (i<l); i+=1ll) {
(u)[(a)[i]]-=1ll;

}
for (int64_t i = prr; (i>r); i-=1ll) {
(u)[(a)[i]]-=1ll;

}
for (int64_t i = (prr+1ll); (i<=r); i+=1ll) {
(u)[(a)[i]]+=1ll;

}
for (int64_t i = (prl-1ll); (i>=l); i-=1ll) {
(u)[(a)[i]]+=1ll;

}
(ans)[ind] = (get)(l, r, k, u, a);

}
String ans_ = String("");
for (int64_t i = 0ll; (i<q); i+=1ll) {
ans_+=(cast_str((ans)[i])+String("\n"));

}
return ans_;
}
int main() {  std::ios::sync_with_stdio(false) ; std::cin.tie(0) ; std::cout.tie(0) ; std::string line, input; while (std::getline(std::cin, line)) { input += line + "\n"; } std::cout << *solve(String(input)).inner; return 0; }/*1653210081.766896*/