← 返回题目列表

Codeforces · 490/D

D. 巧克力

中文机器翻译题面 查看原题

Polycarpus 喜欢给 Paraskevi 送礼物。他买了两块巧克力,每块都是分段的矩形。第一个条是 a1 × b1 段大,第二条是 a2 × b2 段大。

波利卡普斯想在午休时给帕拉斯凯维一份酒吧,自己吃另一份。此外,他想表明波利卡普斯的心智和帕拉斯凯维的美貌是旗鼓相当的,所以两个酒吧的方格数必须相同。

为了使巧克力块具有相同数量的方块,Polycarpus 每分钟吃一小块巧克力。他每分钟都会做以下事情:

- 他要么将一根金条折成两半(垂直或水平),然后吃掉一半的金条,
- 或者他切掉了三分之一的金条(垂直或水平)并吃掉了三分之一的金条。

在第一种情况下,他只剩下一半的酒吧,在第二种情况下,他只剩下三分之二的酒吧。

两种变体并不总是可能的,有时 Polycarpus 无法削掉一半或三分之一。例如,如果金条尺寸为 16 × 23,那么 Polycarpus 可以削掉一半,但不能削掉三分之一。如果木块的尺寸为 20 × 18,那么 Polycarpus 可以削掉一半和三分之一。如果该条是 5 × 7,那么 Polycarpus 无法削掉一半或三分之一。

Polycarpus 需要多少分钟才​​能使两个条形由相同数量的方块组成?不仅要找出所需的最小分钟数,还要找出处理后条形的可能尺寸。

输入

输入的第一行包含整数 a1, b1 (1 ≤ a1, b1 ≤ 109) — 第一个巧克力棒的初始尺寸。输入的第二行包含整数 a2, b2 (1 ≤ a2, b2 ≤ 109) — 第二个条形的初始大小。

您可以使用int64(在Pascal中)、long long(在С++中)、long(在Java中)类型的数据来处理大整数(超过231 - 1)。

输出

在第一行打印 m — 寻求的最小分钟数。在第二行和第三行中,打印在 m 分钟内将钢筋调平后的可能尺寸。使用与输入格式相同的格式打印尺寸。以任意顺序打印尺寸(打印对中的数字)。第二行必须对应于第一条,第三行必须对应于第二条。如果有多个解决方案,请打印其中任何一个。

如果没有解决方案,则打印一行整数-1。

示例

输入 #1

2 6
2 3

输出 #1

1
1 6
2 3

输入 #2

36 5
10 16

输出 #2

3
16 5
5 16

输入 #3

3 5
2 1

输出 #3

-1