# Destiny

## 题目描述

Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l$ $r$ $k$. If there are queries, then they must be answered. Answer for the query is minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than ${r-l+1 \over k}$ times or $-1$ if there is no such number. Help Leha with such a difficult task.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T>
char c; bool flag = false; x = 0;
while (~ c && ! isdigit(c = getchar()) && c != '-') ;
c == '-' && (flag = true, c = getchar());
if (! ~ c) return false;
while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
return (flag && (x = -x), true);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
char c; int len = 0;
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
if (! ~ c) return 0;
while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
return (s[len] = '\0', len);
}
template <typename T>
inline IOManager r(T &x) {
}
template <typename T>
inline void write(T x) {
x < 0 && (putchar('-'), x = -x);
x > 9 && (write(x / 10), true);
putchar(x % 10 + '0');
}
inline void write(char c) {
putchar(c);
}
inline void write(char s[]) {
int pos = 0;
while (s[pos] != '\0') putchar(s[pos ++]);
}
template <typename T>
inline IOManager w(T x) {
write(x); return *this;
}
} io;

struct SegmentTree {
private:
static const int N = 9000000;
int tot;
struct Node {
int val, child[2];
} node[N];
int add_point(int root, int l, int r, int p) {
if (l == r) {
node[++ tot] = (Node) { node[root].val, 0, 0 };
}
int mid = l + r >> 1, rec = ++ tot;
node[rec] = (Node) { 0, 0, 0 };
if (p <= mid) {
node[rec].child[1] = node[root].child[1];
node[rec].child[0] = add_point(node[root].child[0], l, mid, p);
} else {
node[rec].child[0] = node[root].child[0];
node[rec].child[1] = add_point(node[root].child[1], mid + 1, r, p);
}
node[rec].val = node[node[rec].child[0]].val + node[node[rec].child[1]].val;
return rec;
}
int query_point(int root1, int root2, int l, int r, int p) {
if (node[root2].val - node[root1].val < p) return -1;
if (l == r) return node[root2].val - node[root1].val >= p ? l : -1;
int mid = l + r >> 1, res = -1;
if (node[node[root2].child[0]].val - node[node[root1].child[0]].val >= p)
res = query_point(node[root1].child[0], node[root2].child[0], l, mid, p);
if (~ res) return res;
res = query_point(node[root1].child[1], node[root2].child[1], mid + 1, r, p);
return res;
}

public:
int n, cnt, root[N];
root[cnt + 1] = add_point(root[cnt], 1, n, p), ++ cnt;
}
int find(int l, int r, int p) {
return query_point(root[l - 1], root[r], 1, n, p);
}
void print() {
cout << cnt << endl;
for (int i = 1; i <= cnt; ++ i) cout << root[i] << ' ';
cout << endl << tot << endl;
for (int i = 1; i <= tot; ++ i) cout << i << ' ' << node[i].val << ' ' << node[i].child[0] << ' ' << node[i].child[1] << endl;
}
};

struct Solver {
private:
int n, q;
SegmentTree tree;
void input() {
io.r(n).r(q);
tree.n = n;
for (int i = 1; i <= n; ++ i) {
}
}
void process() {
int l, r, k; io.r(l).r(r).r(k);
int p = (r - l + 1) / k + 1;
io.w(tree.find(l, r, p)).w('\n');
}

public:
void solve() {
input(); while (q --) process();
}
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot