C. Сокращение дробей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для запутывания противников Галактическая Империя использует особый формат представления дробей. Дроби представлены как два набора целых чисел. Произведение чисел из первого набора дает числитель дроби, из второго — знаменатель дроби. Однако, обнаружилось, что программы для работы с дробями в таком представлении неполны, в них отсутствует поддержка операции сокращения дробей. Реализуйте эту операцию, и Империя не забудет вас.

Входные данные

В первой строке входного файла через пробел записаны два целых числа n, m (1 ≤ n, m ≤ 105) — количество чисел в первом наборе (числитель) и во втором наборе (знаменатель) соответственно.

Во второй строке записаны n целых чисел через пробел: a1, a2, ..., an (1 ≤ ai ≤ 107) — числа, произведение которых дает числитель.

В третьей строке записаны m целых чисел через пробел: b1, b2, ..., bm (1 ≤ bi ≤ 107) — числа, произведение которых дает знаменатель.

Выходные данные

Выведите ответ на задачу в формате аналогичном формату входных данных. Количества чисел в выводимых наборах nout, mout должны удовлетворять неравенству 1 ≤ nout, mout ≤ 105, а сами числа в наборах aout, i и bout, i — неравенству 1 ≤ aout, i, bout, i ≤ 107.

Числа в строках разделяйте пробельными символами. Выведенная дробь должна быть сокращена, то есть не должно существовать такого целого x (x > 1), что числитель и знаменатель выведенной дроби делятся на x. Если подходящих ответов несколько — выведите любой.

Примеры
Входные данные
3 2
100 5 2
50 10
Выходные данные
2 3
2 1
1 1 1
Входные данные
4 3
2 5 10 20
100 1 3
Выходные данные
1 1
20
3
Примечание

В первом тестовом примере числитель равен 1000, знаменатель — 500. Если сократить дробь 1000/500 на наибольший общий делитель числителя и знаменателя (на 500), получается дробь 2/1.

Во втором тестовом примере числитель равен 2000, знаменатель — 300. Если сократить дробь 2000/300 на наибольший общий делитель числителя и знаменателя (на 100), получается дробь 20/3.