Для запутывания противников Галактическая Империя использует особый формат представления дробей. Дроби представлены как два набора целых чисел. Произведение чисел из первого набора дает числитель дроби, из второго — знаменатель дроби. Однако, обнаружилось, что программы для работы с дробями в таком представлении неполны, в них отсутствует поддержка операции сокращения дробей. Реализуйте эту операцию, и Империя не забудет вас.
Выходные данные
Выведите ответ на задачу в формате аналогичном формату входных данных. Количества чисел в выводимых наборах nout, mout должны удовлетворять неравенству 1 ≤ nout, mout ≤ 105, а сами числа в наборах aout, i и bout, i — неравенству 1 ≤ aout, i, bout, i ≤ 107.
Числа в строках разделяйте пробельными символами. Выведенная дробь должна быть сокращена, то есть не должно существовать такого целого x (x > 1), что числитель и знаменатель выведенной дроби делятся на x. Если подходящих ответов несколько — выведите любой.
Примечание
В первом тестовом примере числитель равен 1000, знаменатель — 500. Если сократить дробь 1000/500 на наибольший общий делитель числителя и знаменателя (на 500), получается дробь 2/1.
Во втором тестовом примере числитель равен 2000, знаменатель — 300. Если сократить дробь 2000/300 на наибольший общий делитель числителя и знаменателя (на 100), получается дробь 20/3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
100 5 2
50 10
|
2 3
2 1
1 1 1
|
|
2
|
4 3
2 5 10 20
100 1 3
|
1 1
20
3
|