P10091 [ROIR 2022] 分数排序 (Day 2)

翻译自 [ROIR 2022 D2T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。

有两个由 $n$ 个不同整数组成的序列 $A = [a_1, a_2, \dots , a_n]$ 和 $B = [b_1, b_2, \dots , b_n]$。将它们组合成 $n^2$ 个分数，形式为 $\frac{a_i}{b_j}$，并将每个分数约分后按递增顺序排序。 给定一个数字 $q$ 和 $q$ 个整数 $c_1, c_2, \dots , c_q$。对于每个 $c_i$，请输出上面所说的 $n^2$ 个分数中第 $c_i$ 小的分数。

第一行包含两个整数 $n$ 和 $q$。 第二行包含 $n$ 个不同的整数 $a_1, a_2, \dots, a_n$。 第三行包含 $n$ 个不同的整数 $b_1, b_2, \dots, b_n$。 第四行包含 $q$ 个不同的整数 $c_1, c_2, \dots, c_q$。

输出 $q$ 行。第 $i$ 行输出按递增顺序得到的第 $c_i$ 个分数。分数 $\frac{p}{q}$ 应以 `p q` 的格式输出，并且应为最简分数。

在样例中，初始的分数列表如下： $$ \left[ \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \frac{3}{5}, \frac{4}{2}, \frac{4}{3}, \frac{4}{4}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \frac{2}{5} \right], $$ 经过约分后，得到： $$ \left[ \frac{3}{2}, \frac{1}{1}, \frac{3}{4}, \frac{3}{5}, \frac{2}{1}, \frac{4}{3}, \frac{1}{1}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{1}, \frac{2}{3}, \frac{1}{2}, \frac{2}{5} \right], $$ 最后按递增顺序排序，得到： $$ \left[ \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}, \frac{1}{1}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{2}{1} \right]. $$ 本题使用捆绑测试。 | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $14$ | $n\le50$ | | $2$ | $13$ | $n\le500$ | | $3$ | $15$ | $q,c_i\le100$ | | $4$ | $21$ | $c_i\le10^5$ | | $5$ | $37$ | | 对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$1 \leq q \leq 10^5$ 且 $q \leq n^2,n\times q\le10^5$（所以实际上 $q\le1000\sqrt[3]{10}\approx2154$），$1 \leq a_i,b_i \leq 10^6$，$1 \leq c_i \leq n^2$。