[AdditionalFile4309.zip](file://AdditionalFile4309.zip?type=additional_file)

#4309. 「ROIR 2022 Day2」分数排序

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI Regional 2022 Day2 T2. Сортировка дробей

黑板上写了两个由 $n$ 个不同整数组成的序列：$A = [a_1, a_2, \ldots, a_n]$ 和 $B = [b_1, b_2, \ldots, b_n]$。

我们可以从中构造出 $n^2$ 个分数，形式为 $a_i / b_j$，然后将每个分数化简并按非递减顺序排序。

给定一个整数 $q$ 和 $q$ 个整数 $c_1, c_2, \ldots, c_q$。对于每个 $j$，输出排序后第 $c_j$ 个分数。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \le n \le 10^5, 1 \le q \le 10^5, q \le n^2)$。

此外，还满足 $n \cdot q \le 10^5$。

第二行包含 $n$ 个不同的整数 $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^6)$。

第三行包含 $n$ 个不同的整数 $b_1, b_2, \ldots, b_n$ $(1 \le b_i \le 10^6)$。

第四行包含 $q$ 个不同的整数 $c_1, c_2, \ldots, c_q$ $(1 \le c_i \le n^2)$。

输出格式

输出 $q$ 行。第 $j$ 行输出排序后第 $c_j$ 个分数，格式为 p q，表示分数 $\frac{p}{q}$，且分数应为不可约分数。

样例

输入

4 8
3 4 1 2
2 3 4 5
1 16 2 4 5 6 10 15

输出

1 5
2 1
1 4
2 5
1 2
1 2
4 5
3 2

在样例中，初始分数为：

$$\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 \le 50$	无
$2$	$13$	$n \le 500$	$1$
$3$	$15$	$q \le 100$，$c_i \le 100$	无
$4$	$21$	$c_i \le 10^5$	$3$
$5$	$37$	无	$1\sim 4$