Задача №115203. Сортировка дробей
На доске выписано две последовательности из \(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 | первая ошибка |
В примере дроби исходно равны: \(\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].\)
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