Processing math: 100%

Задача 2. Сортировка дробей

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

На доске выписано две последовательности из n различных целых чисел: A=[a1,a2,,an] и B=[b1,b2,,bn].

Составим из них n2 дробей вида ai/bj, сократим каждую дробь и отсортируем их по неубыванию.

Задано число q и q целых чисел c1,c2,,cq. Для каждого j следует выдать cj-ю в неубывающем порядке дробь из получившихся.

Формат входных данных

На первой строке ввода находятся числа n и q (1n105, 1q105, qn2).

Дополнительно выполняется неравенство nq105.

На второй строке ввода находятся n различных целых чисел a1,a2,,an (1ai106).

На третьей строке ввода находятся n различных целых чисел b1,b2,,bn (1bi106).

На четвертой строке ввода находятся q различных целых чисел c1,c2,,cq (1cin2).

Формат выходных данных

Выведите q строк. На j-й строке выведите cj-ю по неубыванию дробь среди получившихся. Дробь p/q следует выводить в формате {p q}, дробь должна быть несократимой.

Ограничения

1n105, 1q105, qn2

nq105

1ai106

1bi106

1cin2

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
114n50первая ошибка
213n5001первая ошибка
315q100, ci100первая ошибка
421ci1053первая ошибка
53714первая ошибка

Пояснение к примеру

В примере дроби исходно равны:

[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
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

0.063s 0.008s 13