题目背景

翻译自 ROIR 2022 D2T2。

题目描述

有两个由 $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 的格式输出，并且应为最简分数。

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\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$。