# [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` 的格式输出，并且应为最简分数。

## 样例 #1

### 样例输入 #1

```
4 8
3 4 1 2
2 3 4 5
1 16 2 4 5 6 10 15
```

### 样例输出 #1

```
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$。