Входной файл: | Стандартный вход | Ограничение времени: | 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 |
|
|