Сортировка дробей
(Время: 3 сек. Память: 32 Мб Сложность: 48%)
На доске выписано две последовательности из n различных целых чисел: A = [a1, a2, ... , an] и B = [b1, b2, ... , bn].
Составим из них n2 дробей вида ai/bj , сократим каждую дробь и отсортируем их по неубыванию. Задано число q и q целых чисел c1, c2, ... , cq. Для каждого j следует выдать cj-ю в неубывающем порядке дробь из получившихся.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа 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).
Выходные данные
В выходной файл OUTPUT.TXT выведите q строк. На j-й строке выведите cj-ю по неубыванию дробь среди получившихся. Дробь p/q следует выводить в формате «p q», при этом дробь должна быть несократимой.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 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 |
Пояснение
В примере дроби исходно равны:
Дроби после сокращения:
Дроби после сортировки:
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
