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

Условие

На доске выписано две последовательности из n различных целых чисел: A = [a₁, a₂, …, a_n] и B = [b₁, b₂, …, b_n].

Составим из них n² дробей вида a_i / b_j, сократим каждую дробь и отсортируем их по неубыванию.

Задано число q и q целых чисел c₁, c₂, …, c_q. Для каждого j следует выдать c_j-ю в неубывающем порядке дробь из получившихся.

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

На первой строке ввода находятся числа n и q (1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵, q ≤ n²).

Дополнительно выполняется неравенство n ⋅ q ≤ 10⁵.

На второй строке ввода находятся n различных целых чисел a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁶).

На третьей строке ввода находятся n различных целых чисел b₁, b₂, …, b_n (1 ≤ b_i ≤ 10⁶).

На четвертой строке ввода находятся q различных целых чисел c₁, c₂, …, c_q (1 ≤ c_i ≤ n²).

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

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

Ограничения

1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵, q ≤ n²

n ⋅ q ≤ 10⁵

1 ≤ a_i ≤ 10⁶

1 ≤ b_i ≤ 10⁶

1 ≤ c_i ≤ n²

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

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

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

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

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

Примеры тестов

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