Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 100 |
На доске выписано две последовательности из n различных целых чисел: A = [a1, a2, …, an] и B = [b1, b2, …, bn].
Составим из них n2 дробей вида ai / bj, сократим каждую дробь и отсортируем их по неубыванию.
Задано число q и q целых чисел c1, c2, …, cq. Для каждого j следует выдать cj-ю в неубывающем порядке дробь из получившихся.
На первой строке ввода находятся числа n и q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105, q ≤ n2).
Дополнительно выполняется неравенство n ⋅ q ≤ 105.
На второй строке ввода находятся n различных целых чисел a1, a2, …, an (1 ≤ ai ≤ 106).
На третьей строке ввода находятся n различных целых чисел b1, b2, …, bn (1 ≤ bi ≤ 106).
На четвертой строке ввода находятся q различных целых чисел c1, c2, …, cq (1 ≤ ci ≤ n2).
Выведите q строк. На j-й строке выведите cj-ю по неубыванию дробь среди получившихся. Дробь p / q следует выводить в формате {p q}, дробь должна быть несократимой.
1 ≤ n ≤ 105, 1 ≤ q ≤ 105, q ≤ n2
n ⋅ q ≤ 105
1 ≤ ai ≤ 106
1 ≤ bi ≤ 106
1 ≤ ci ≤ n2
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 14 | n ≤ 50 | первая ошибка | |
2 | 13 | n ≤ 500 | 1 | первая ошибка |
3 | 15 | q ≤ 100, ci ≤ 100 | первая ошибка | |
4 | 21 | ci ≤ 105 | 3 | первая ошибка |
5 | 37 | 1 − 4 | первая ошибка |
В примере дроби исходно равны:
[32, 33, 34, 35, 42, 43, 44, 45, 12, 13, 14, 15, 22, 23, 24, 25],
после сокращения
[32, 11, 34, 35, 21, 43, 11, 45, 12, 13, 14, 15, 11, 23, 12, 25],
после сортировки
[15, 14, 13, 25, 12, 12, 35, 23, 34, 45, 11, 11, 11, 43, 32, 21].
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|