D. Шоколадки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Поликарпу нравится делать подарки Прасковье. Вот и сейчас он купил две плитки шоколада, каждая из них имеет форму прямоугольника из долек. Первая плитка имеет размеры a1 × b1 долек, а вторая — a2 × b2 долек.

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

Чтобы сделать плитки равными по количеству долек, Поликарп каждую минуту съедает немного шоколада. Каждую минуту он:

  • либо разламывает одну плитку ровно пополам (вертикально или горизонтально) и съедает ровно половину шоколадки,
  • либо отламывает от плитки ровно одну треть (вертикально или горизонтально) и съедает ровно треть шоколадки.

В первом случае от плитки останется половина, а во втором — две трети.

Не всегда возможны оба развития событий, а иногда бывает, что Поликарп вообще не может отломить половину или треть. Например, если плитка имеет размер 16 × 23, то от нее можно отломить половину, но нельзя одну треть. Если плитка имеет размер 20 × 18, то от нее можно отломить как половину, так и треть. Если плитка имеет размер 5 × 7, то отломить как половину так и треть невозможно.

Какое минимальное количество минут понадобится Поликарпу, чтобы сделать обе плитки одинаковыми по количеству долек в них? Найдите не только искомое минимальное количество минут, но и возможные размеры плиток после их вынужденного «уравнивания».

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

В первой строке входных данных записаны целые числа a1, b1 (1 ≤ a1, b1 ≤ 109) — первоначальные размеры первой шоколадки. Во второй строке входных данных записаны целые числа a2, b2 (1 ≤ a2, b2 ≤ 109) — первоначальные размеры второй шоколадки.

Вы можете использовать типы данных int64 (в Паскале), long long (в С++), long (в Java) для работы с большими целыми числами (превосходящими 231 - 1).

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

В первую строку выведите m — искомое минимальное количество минут. Во вторую и третью строки выведите возможные размеры плиток после их уравнивания за m минут. Выводите размеры, используя формат, аналогичный формату входных данных. Размеры (числа в выводимых парах) выводите в любом порядке. Вторая строка должна соответствовать первой шоколадке, а третья — второй. Если решений несколько, выведите любое из них.

Если решения не существует, то выведите единственную строку с числом -1.

Примеры
Входные данные
2 6
2 3
Выходные данные
1
1 6
2 3
Входные данные
36 5
10 16
Выходные данные
3
16 5
5 16
Входные данные
3 5
2 1
Выходные данные
-1