Сортировка дробей
На доске выписано две последовательности из $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$ следует выводить в формате «p q», дробь должна быть несократимой.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 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–4 | первая ошибка |
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].$$
Задача на Codeforces (контест gym/103533, задача 6, © Codeforces.com)