有 $n$ 个选手参加了一场比赛，其中第 $i$ 个选手在笔试环节中得到了 $a_i$ 分。主办方一共有 $q$ 个会场，第 $i$ 个会场最多可容纳 $k_i$ 人，在接下来的面试环节中，主办方会随机选择一个会场，并根据面试会场的最大可容纳人数确定分数线 $x$，以使得在笔试中分数 $\geqslant x$ 的所有选手都能够参加面试并且人数不超过会场的最大可容纳人数。特别地，笔试分数为 $0$ 分的选手无论会场最大可容纳人数是多少，都不能够参加面试环节。

现在你想知道，对于所有的 $1\leqslant i\leqslant n$，如果主办方选择了第 $i$ 个会场，至少要将分数线划为多少分，使得能够参加面试环节的选手人数 $\geqslant k_i$。

数据范围：

• $1\leqslant n,q\leqslant 10^5$。
• $0\leqslant a_i\leqslant 10^6$，$0\leqslant k_i\leqslant n$。

Translated by Eason_AC
2021.12.23