抽奖

题目描述

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，以及 $Q$ 次询问。

每次询问给出四个整数 $l,r,p,q$。设整数 $x$ 在区间 $a_l,a_{l+1},\dots,a_r$ 中出现的次数为 $cnt_x$。

如果存在整数 $x$ 满足

就输出任意一个这样的 $x$；如果不存在，输出 $-1$。

输入格式

第一行两个整数 $n,Q$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $Q$ 行，每行四个整数 $l,r,p,q$，表示一次询问。

输出格式

共 $Q$ 行，每行一个整数：存在满足条件的 $x$ 则输出任意一个这样的 $x$，否则输出 $-1$。

数据范围

• $1 \le n,Q \le 10^5$
• $1 \le a_i \le 10^9$
• $1 \le l \le r \le n$
• $1 \le p < q \le 10^9$，且保证 $\frac{p}{q} \ge \frac{1}{10}$

输入输出样例

样例 1

输入：

5 4
1 2 1 2 1
1 5 1 2
1 5 1 10
2 5 1 10
1 1 1 2

输出：

1
1
2
1

样例解释

• 询问 $[1,5]$，阈值 $\frac12$：$1$ 出现 $3$ 次，$3>2.5$，输出 $1$；
• 询问 $[1,5]$，阈值 $\frac1{10}$：$1$ 出现 $3$ 次，$3>0.5$，输出 $1$；
• 询问 $[2,5]$，阈值 $\frac1{10}$：区间是 $2,1,2,1$，$2$ 出现 $2$ 次，$2>0.4$，输出 $2$；
• 询问 $[1,1]$，阈值 $\frac12$：$1$ 出现 $1$ 次，$1>0.5$，输出 $1$。

说明/提示

• 若有多组解，输出任意一组即可，本题使用特殊评测（Special Judge）。
• 保证 $\frac pq \ge \frac{1}{10}$，也就是说，一旦有答案，它在区间内的出现次数就严格大于区间长度的 $10\%$。
• 时间限制 $2$ 秒，空间限制 $256$ MB。