Задача 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 (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

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

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
114n ≤ 50первая ошибка
213n ≤ 5001первая ошибка
315q ≤ 100, ci ≤ 100первая ошибка
421ci ≤ 1053первая ошибка
5371 − 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
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.082s 0.011s 13