Polycarpus likes giving presents to Paraskevi. He has bought two chocolate bars, each of them has the shape of a segmented rectangle. The first bar is a_1 × b_1 segments large and the second one is a_2 × b_2 segments large.

Polycarpus wants to give Paraskevi one of the bars at the lunch break and eat the other one himself. Besides, he wants to show that Polycarpus's mind and Paraskevi's beauty are equally matched, so the two bars must have the same number of squares.

To make the bars have the same number of squares, Polycarpus eats a little piece of chocolate each minute. Each minute he does the following:  he either breaks one bar exactly in half (vertically or horizontally) and eats exactly a half of the bar,  or he chips of exactly one third of a bar (vertically or horizontally) and eats exactly a third of the bar. 

In the first case he is left with a half, of the bar and in the second case he is left with two thirds of the bar.

Both variants aren't always possible, and sometimes Polycarpus cannot chip off a half nor a third. For example, if the bar is 16 × 23, then Polycarpus can chip off a half, but not a third. If the bar is 20 × 18, then Polycarpus can chip off both a half and a third. If the bar is 5 × 7, then Polycarpus cannot chip off a half nor a third.

What is the minimum number of minutes Polycarpus needs to make two bars consist of the same number of squares? Find not only the required minimum number of minutes, but also the possible sizes of the bars after the process.


-----Input-----

The first line of the input contains integers a_1, b_1 (1 ≤ a_1, b_1 ≤ 10^9) — the initial sizes of the first chocolate bar. The second line of the input contains integers a_2, b_2 (1 ≤ a_2, b_2 ≤ 10^9) — the initial sizes of the second bar.

You can use the data of type int64 (in Pascal), long long (in С++), long (in Java) to process large integers (exceeding 2^31 - 1).


-----Output-----

In the first line print m — the sought minimum number of minutes. In the second and third line print the possible sizes of the bars after they are leveled in m minutes. Print the sizes using the format identical to the input format. Print the sizes (the numbers in the printed pairs) in any order. The second line must correspond to the first bar and the third line must correspond to the second bar. If there are multiple solutions, print any of them.

If there is no solution, print a single line with integer -1.


-----Examples-----
Input
2 6
2 3

Output
1
1 6
2 3

Input
36 5
10 16

Output
3
16 5
5 16

Input
3 5
2 1

Output
-1

Source: codeforces | Difficulty: HARD
Tags: Number theory

Graph traversal

Mathematics

Complete search


Solutions:
__author__ = 'zhan'
import time
[a1, b1] = [int(i) for i in input().split()]
[a2, b2] = [int(i) for i in input().split()]
t0 = time.time()
q1 = [[a1, b1, 0]]
q2 = [[a2, b2, 0]]
tested1 = []
tested2 = []
tested_total1 = []
tested_total2 = []

def equal(t, q):
	lo = 0
	hi = len(q)
	while True:
		if lo >= hi:
			return False
		m = (lo + hi) // 2
		p = q[m]
		temp = p[0] * p[1]
		if t == temp:
			return [p[0], p[1], p[2]]
		if t < temp:
			lo = m + 1
		elif t > temp:
			hi = m

def found(key, a):
	lo = 0
	hi = len(a)
	while True:
		if lo >= hi:
			return False
		m = (lo + hi) // 2
		p = a[m]
		if key[0] == p[0] and key[1] == p[1]:
			return True
		if key[0] < p[0] or (key[0] == p[0] and key[1] < p[1]):
			lo = m + 1
		if key[0] > p[0] or (key[0] == p[0] and key[1] > p[1]):
			hi = m
while True:
	if len(q1) > 0 and len(q2) > 0:
		total1 = q1[0][0] * q1[0][1]
		total2 = q2[0][0] * q2[0][1]
		if total1 > total2:
			ans = equal(total1, q2)
			if ans:
				print(str(ans[2] + q1[0][2]) + '\n' + str(q1[0][0]) + ' ' + str(q1[0][1]) + '\n' + str(ans[0]) + ' ' + str(ans[1]))
			else:
				if not q1[0][0] & 1:
					tt = [q1[0][0] // 2, q1[0][1], q1[0][2] + 1]
					if not [tt[0], tt[1]] in tested1 and (not tt[0] * tt[1] in tested_total1):
						tested1.append([tt[0], tt[1]])
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q2)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				if q1[0][0] % 3 == 0:
					tt = [q1[0][0] // 3 * 2, q1[0][1], q1[0][2] + 1]
					if not [tt[0], tt[1]] in tested1 and (not tt[0] * tt[1] in tested_total1):
						tested1.append([tt[0], tt[1]])
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q2)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				if not q1[0][1] & 1:
					tt = [q1[0][0], q1[0][1] // 2, q1[0][2] + 1]
					if not [tt[0], tt[1]] in tested1 and (not tt[0] * tt[1] in tested_total1):
						tested1.append([tt[0], tt[1]])
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q2)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				if q1[0][1] % 3 == 0:
					tt = [q1[0][0], q1[0][1] // 3 * 2, q1[0][2] + 1]
					if not [tt[0], tt[1]] in tested1 and (not tt[0] * tt[1] in tested_total1):
						tested1.append([tt[0], tt[1]])
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q2)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				q1.pop(0)
				q1.sort(key=lambda x: x[0] * x[1], reverse=True)
		elif total1 < total2:
			ans = equal(total2, q1)
			if ans:
				print(str(ans[2] + q2[0][2]) + '\n' + str(ans[0]) + ' ' + str(ans[1]) + '\n' + str(q2[0][0]) + ' ' + str(q2[0][1]))
				break
			else:
				if not q2[0][0] & 1:
					tt = [q2[0][0] // 2, q2[0][1], q2[0][2] + 1]
					if not [tt[0], tt[1]] in tested2 and (not tt[0] * tt[1] in tested_total2):
						tested2.append([tt[0], tt[1]])
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q1)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				if q2[0][0] % 3 == 0:
					tt = [q2[0][0] // 3 * 2, q2[0][1], q2[0][2] + 1]
					if not [tt[0], tt[1]] in tested2 and (not tt[0] * tt[1] in tested_total2):
						tested2.append([tt[0], tt[1]])
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q1)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				if not q2[0][1] & 1:
					tt = [q2[0][0], q2[0][1] // 2, q2[0][2] + 1]
					if not [tt[0], tt[1]] in tested2 and (not tt[0] * tt[1] in tested_total2):
						tested2.append([tt[0], tt[1]])
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q1)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				if q2[0][1] % 3 == 0:
					tt = [q2[0][0], q2[0][1] // 3 * 2, q2[0][2] + 1]
					if not [tt[0], tt[1]] in tested2 and (not tt[0] * tt[1] in tested_total2):
						tested2.append([tt[0], tt[1]])
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
						an = equal(tt[0] * tt[1], q1)
						if ans:
							print(str(an[2] + tt[2]) + '\n' + str(tt[0]) + ' ' + str(tt[1]) + '\n' + str(an[0]) + ' ' + str(an[1]))
				q2.pop(0)
				q2.sort(key=lambda x: x[0] * x[1], reverse=True)
		else:
			print(str(q1[0][2] + q2[0][2]) + '\n' + str(q1[0][0]) + ' ' + str(q1[0][1]) + '\n' + str(q2[0][0]) + ' ' + str(q2[0][1]))
			break
	else:
		print(-1)
		break
t1 = time.time()


def dfs(x, d, g):
	g[x] = set()
	d[x] = 1
	if x % 2 == 0:
		next_ = x // 2
		if next_ not in d:
			g[x].add(next_)
			dfs(next_, d, g)
		elif next_ not in g[x]:
			g[x].add(next_)
	if x % 3 == 0:
		next_ = x // 3 * 2
		if next_ not in d:
			g[x].add(next_)
			dfs(next_, d, g)
		elif next_ not in g[x]:
			g[x].add(next_)

def bfs(x, g):

	def add_prev(prev, cur_, next_):
		if next_ * 2 == cur_:
			prev[next_] = [cur_, 2]
		else:
			prev[next_] = [cur_, 3]
	min_ = {}
	s = [x]
	min_[x] = 0
	i = 0
	prev = {}
	while i < len(s):
		cur = s[i]
		for next_ in g[cur]:
			if next_ not in min_:
				min_[next_] = min_[cur] + 1
				s.append(next_)
				add_prev(prev, cur, next_)
			elif min_[cur] + 1 < min_[next_]:
				min_[next_] = min_[cur] + 1
				add_prev(prev, cur, next_)
		i += 1
	return (min_, prev)

def find(a1, b1, a2, b2, min1, prev1, min2, prev2):

	def process(a, b, type_):
		if type_ == 2:
			if a % 2 == 0:
				return (a // 2, b)
			else:
				return (a, b // 2)
		elif a % 3 == 0:
			return (a // 3 * 2, b)
		else:
			return (a, b // 3 * 2)
	x1 = a1 * b1
	x2 = a2 * b2
	min_ = float('inf')
	num = None
	for x in min1:
		if x in min2:
			if min_ > min1[x] + min2[x]:
				min_ = min1[x] + min2[x]
				num = x
	if num == None:
		return (-1, None, None)
	cur1 = num
	arr1 = []
	while cur1 != x1:
		(prev_, type_) = prev1[cur1]
		arr1.append(type_)
		cur1 = prev_
	cur2 = num
	arr2 = []
	while cur2 != x2:
		(prev_, type_) = prev2[cur2]
		arr2.append(type_)
		cur2 = prev_
	for type_ in arr1[::-1]:
		(a1, b1) = process(a1, b1, type_)
	for type_ in arr2[::-1]:
		(a2, b2) = process(a2, b2, type_)
	return (min_, [a1, b1], [a2, b2])
(a1, b1) = map(int, input().split())
(a2, b2) = map(int, input().split())
(d1, g1, d2, g2) = ({}, {}, {}, {})
dfs(a1 * b1, d1, g1)
dfs(a2 * b2, d2, g2)
(min1, prev1) = bfs(a1 * b1, g1)
(min2, prev2) = bfs(a2 * b2, g2)
(ans, arr1, arr2) = find(a1, b1, a2, b2, min1, prev1, min2, prev2)
if ans == -1:
	print(-1)
else:
	print(ans)
	print(str(arr1[0]) + ' ' + str(arr1[1]))
	print(str(arr2[0]) + ' ' + str(arr2[1]))


__author__ = 'zhan'
[a1, b1] = [int(i) for i in input().split()]
[a2, b2] = [int(i) for i in input().split()]
q = [[[a1, b1, 0]], [[a2, b2, 0]]]
total = [0, 0]
tested = [[], []]

def equal(t, q):
	lo = 0
	hi = len(q)
	while True:
		if lo >= hi:
			return False
		m = (lo + hi) // 2
		p = q[m]
		temp = p[0] * p[1]
		if t == temp:
			return [p[0], p[1], p[2]]
		if t < temp:
			lo = m + 1
		elif t > temp:
			hi = m

def expand(i):
	ans = equal(total[i], q[(i + 1) % 2])
	if ans:
		print(str(ans[2] + q[i][0][2]) + '\n' + str(q[i][0][0]) + ' ' + str(q[i][0][1]) + '\n' + str(ans[0]) + ' ' + str(ans[1]))
	else:
		if not q[i][0][0] & 1:
			tt = [q[i][0][0] // 2, q[i][0][1], q[i][0][2] + 1]
			if not tt[0] * tt[1] in tested[i]:
				q[i].append(tt)
				tested[i].append(tt[0] * tt[1])
		if q[i][0][0] % 3 == 0:
			tt = [q[i][0][0] // 3 * 2, q[i][0][1], q[i][0][2] + 1]
			if not tt[0] * tt[1] in tested[i]:
				q[i].append(tt)
				tested[i].append(tt[0] * tt[1])
		if not q[i][0][1] & 1:
			tt = [q[i][0][0], q[i][0][1] // 2, q[i][0][2] + 1]
			if not tt[0] * tt[1] in tested[i]:
				q[i].append(tt)
				tested[i].append(tt[0] * tt[1])
		if q[i][0][1] % 3 == 0:
			tt = [q[i][0][0], q[i][0][1] // 3 * 2, q[i][0][2] + 1]
			if not tt[0] * tt[1] in tested[i]:
				q[i].append(tt)
				tested[i].append(tt[0] * tt[1])
		q[i].pop(0)
		q[i].sort(key=lambda x: x[0] * x[1], reverse=True)
while True:
	if len(q[0]) > 0 and len(q[1]) > 0:
		total[0] = q[0][0][0] * q[0][0][1]
		total[1] = q[1][0][0] * q[1][0][1]
		if total[0] > total[1]:
			expand(0)
		elif total[0] < total[1]:
			expand(1)
		else:
			print(str(q[0][0][2] + q[1][0][2]) + '\n' + str(q[0][0][0]) + ' ' + str(q[0][0][1]) + '\n' + str(q[1][0][0]) + ' ' + str(q[1][0][1]))
			break
	else:
		print(-1)
		break


(a1, b1) = map(int, input().split())
(a2, b2) = map(int, input().split())
(F, S) = ([a1, b1], [a2, b2])
A = dict()
B = dict()
A[2] = A[3] = B[2] = B[3] = 0
i = 2
while i ** 2 <= a1:
	if a1 % i == 0:
		A[i] = 0
		while a1 % i == 0:
			A[i] += 1
			a1 //= i
	i += 1
if a1 > 1:
	if not a1 in A:
		A[a1] = 0
	A[a1] += 1
i = 2
while i ** 2 <= b1:
	if b1 % i == 0:
		if not i in A:
			A[i] = 0
		while b1 % i == 0:
			A[i] += 1
			b1 //= i
	i += 1
if b1 > 1:
	if not b1 in A:
		A[b1] = 0
	A[b1] += 1
i = 2
while i ** 2 <= a2:
	if a2 % i == 0:
		B[i] = 0
		while a2 % i == 0:
			B[i] += 1
			a2 //= i
	i += 1
if a2 > 1:
	if not a2 in B:
		B[a2] = 0
	B[a2] += 1
i = 2
while i ** 2 <= b2:
	if b2 % i == 0:
		if not i in B:
			B[i] = 0
		while b2 % i == 0:
			B[i] += 1
			b2 //= i
	i += 1
if b2 > 1:
	if not b2 in B:
		B[b2] = 0
	B[b2] += 1
C1 = sorted([i for i in A.keys() if not i in {2, 3}])
C2 = sorted([i for i in B.keys() if not i in {2, 3}])
if C1 != C2:
	print(-1)
else:
	flag = True
	for i in C1:
		if A[i] != B[i]:
			flag = False
	if not flag:
		print(-1)
	else:
		Min = 0
		x = A[3] - B[3]
		Min += abs(x)
		if x >= 0:
			A[2] += x
			while x > 0 and F[0] % 3 == 0:
				F[0] //= 3
				F[0] *= 2
				x -= 1
			while x > 0 and F[1] % 3 == 0:
				F[1] //= 3
				F[1] *= 2
				x -= 1
		else:
			B[2] -= x
			while x < 0 and S[0] % 3 == 0:
				S[0] //= 3
				S[0] *= 2
				x += 1
			while x < 0 and S[1] % 3 == 0:
				S[1] //= 3
				S[1] *= 2
				x += 1
		if x != 0:
			flag = False
		x = A[2] - B[2]
		Min += abs(x)
		if x >= 0:
			while x > 0 and F[0] % 2 == 0:
				F[0] //= 2
				x -= 1
			while x > 0 and F[1] % 2 == 0:
				F[1] //= 2
				x -= 1
		else:
			while x < 0 and S[0] % 2 == 0:
				S[0] //= 2
				x += 1
			while x < 0 and S[1] % 2 == 0:
				S[1] //= 2
				x += 1
		if x != 0:
			flag = False
		if flag:
			print(Min)
			print(*F)
			print(*S)
		else:
			print(-1)


f = lambda : map(int, input().split())
(a, b) = f()
(c, d) = f()

def g(p, k):
	s = 1
	while k % p ** s == 0:
		s += 1
	return s - 1
(a3, b3, c3, d3) = (g(3, a), g(3, b), g(3, c), g(3, d))
(a2, b2, c2, d2) = (g(2, a), g(2, b), g(2, c), g(2, d))
(ab3, cd3) = (a3 + b3, c3 + d3)
(ab2, cd2) = (a2 + b2, c2 + d2)
ab = a * b * pow(2, cd2) * pow(3, cd3)
cd = c * d * pow(2, ab2) * pow(3, ab3)
if ab != cd:
	print(-1)
	return
(k, s2, s3) = (1000000000.0, 0, 0)
for t3 in range(min(ab3, cd3) + 1):
	k3 = ab3 + cd3 - 2 * t3
	for t2 in range(min(ab2 + ab3, cd2 + cd3) - t3 + 1):
		k2 = k3 + ab2 + cd2 - 2 * t2
		if k2 + k3 < k:
			k = k2 + k3
			(s2, s3) = (t2, t3)
t3 = ab3 - s3
while t3 and a % 3 == 0:
	a = 2 * a // 3
	t3 -= 1
while t3 and b % 3 == 0:
	b = 2 * b // 3
	t3 -= 1
t2 = ab3 - s3 + ab2 - s2
while t2 and a % 2 == 0:
	a = a // 2
	t2 -= 1
while t2 and b % 2 == 0:
	b = b // 2
	t2 -= 1
t3 = cd3 - s3
while t3 and c % 3 == 0:
	c = 2 * c // 3
	t3 -= 1
while t3 and d % 3 == 0:
	d = 2 * d // 3
	t3 -= 1
t2 = cd3 - s3 + cd2 - s2
while t2 and c % 2 == 0:
	c = c // 2
	t2 -= 1
while t2 and d % 2 == 0:
	d = d // 2
	t2 -= 1
print(k)
print(a, b)
print(c, d)


(a1, b1) = map(int, input().split())
(a2, b2) = map(int, input().split())
a10 = a1
b10 = b1
a20 = a2
b20 = b2
a_divs = list()
b_divs = list()
div = 2
while a1 > 1 and div < a1 ** 0.5 + 1:
	while a1 % div == 0:
		a_divs.append(div)
		a1 //= div
	div += 1
if a1 > 1:
	a_divs.append(a1)
div = 2
while b1 > 1 and div < b1 ** 0.5 + 1:
	while b1 % div == 0:
		a_divs.append(div)
		b1 //= div
	div += 1
if b1 > 1:
	a_divs.append(b1)
div = 2
while a2 > 1 and div < a2 ** 0.5 + 1:
	while a2 % div == 0:
		b_divs.append(div)
		a2 //= div
	div += 1
if a2 > 1:
	b_divs.append(a2)
div = 2
while b2 > 1 and div < b2 ** 0.5 + 1:
	while b2 % div == 0:
		b_divs.append(div)
		b2 //= div
	div += 1
if b2 > 1:
	b_divs.append(b2)
a1 = a10
b1 = b10
a2 = a20
b2 = b20
a_divs.sort()
b_divs.sort()
na = len(a_divs)
nb = len(b_divs)
a = 1
while na > 0 and a_divs[-1] > 3:
	a *= a_divs[-1]
	a_divs = a_divs[:-1]
	na -= 1
b = 1
while nb > 0 and b_divs[-1] > 3:
	b *= b_divs[-1]
	b_divs = b_divs[:-1]
	nb -= 1
if a != b:
	print(-1)
else:
	ans = 0
	a_3 = a_divs.count(3)
	a_2 = a_divs.count(2)
	b_3 = b_divs.count(3)
	b_2 = b_divs.count(2)
	if a_3 > b_3:
		for i in range(a_3 - b_3):
			a_divs[a_divs.index(3)] = 2
			a_3 -= 1
			a_2 += 1
			ans += 1
			if a1 % 3 == 0:
				a1 //= 3
				a1 *= 2
			else:
				b1 //= 3
				b1 *= 2
	else:
		for i in range(b_3 - a_3):
			b_divs[b_divs.index(3)] = 2
			b_3 -= 1
			b_2 += 1
			ans += 1
			if a2 % 3 == 0:
				a2 //= 3
				a2 *= 2
			else:
				b2 //= 3
				b2 *= 2
	if a_2 > b_2:
		for i in range(a_2 - b_2):
			a_2 -= 1
			ans += 1
			if a1 % 2 == 0:
				a1 //= 2
			else:
				b1 //= 2
	else:
		for i in range(b_2 - a_2):
			b_2 -= 1
			ans += 1
			if a2 % 2 == 0:
				a2 //= 2
			else:
				b2 //= 2
	print(ans)
	print(a1, b1)
	print(a2, b2)


def decomp(a):
	cnt2 = 0
	while a % 2 == 0:
		a = a // 2
		cnt2 += 1
	cnt3 = 0
	while a % 3 == 0:
		a = a // 3
		cnt3 += 1
	return (a, cnt2, cnt3)

def cut(a, b, d, p):
	while d > 0:
		if a % p == 0:
			a = (p - 1) * a // p
			d = d - 1
		elif b % p == 0:
			b = (p - 1) * b // p
			d = d - 1
	return (a, b)
(a1, b1) = [int(s) for s in input().split()]
(a2, b2) = [int(s) for s in input().split()]
(u1, n2a1, n3a1) = decomp(a1)
(v1, n2b1, n3b1) = decomp(b1)
(u2, n2a2, n3a2) = decomp(a2)
(v2, n2b2, n3b2) = decomp(b2)
if u1 * v1 != u2 * v2:
	print(-1)
else:
	n = n2a1 + n2b1
	m = n3a1 + n3b1
	x = n2a2 + n2b2
	y = n3a2 + n3b2
	d3 = abs(m - y)
	if m > y:
		n += d3
		(a1, b1) = cut(a1, b1, d3, 3)
	else:
		x += d3
		(a2, b2) = cut(a2, b2, d3, 3)
	d2 = abs(n - x)
	if n > x:
		(a1, b1) = cut(a1, b1, d2, 2)
	else:
		(a2, b2) = cut(a2, b2, d2, 2)
	m = d2 + d3
	print(m)
	print(a1, b1)
	print(a2, b2)


def fact(a, b):
	ans = 0
	while a % b == 0:
		ans += 1
		a //= b
	return ans

def fact_remove(a, b):
	c = a * b
	while c % 2 == 0:
		c //= 2
	while c % 3 == 0:
		c //= 3
	return c
(a1, b1) = map(int, input().split(' '))
(a2, b2) = map(int, input().split(' '))
if fact_remove(a1, b1) != fact_remove(a2, b2):
	print(-1)
else:
	ans = [0, 0, 0, 0]
	c1 = a1 * b1
	c2 = a2 * b2
	k1 = fact(c1, 3)
	k2 = fact(c2, 3)
	if k1 > k2:
		ans[1] = k1 - k2
		c1 /= 3 ** ans[1]
		c1 *= 2 ** ans[1]
	elif k1 < k2:
		ans[3] = k2 - k1
		c2 /= 3 ** ans[3]
		c2 *= 2 ** ans[3]
	k1 = fact(c1, 2)
	k2 = fact(c2, 2)
	if k1 > k2:
		ans[0] = k1 - k2
		c1 /= 2 ** ans[0]
	elif k1 < k2:
		ans[2] = k2 - k1
		c2 /= 2 ** ans[2]
	if c1 != c2:
		print(-1)
	else:
		print(sum(ans))
		while a1 % 3 == 0 and ans[1] > 0:
			a1 //= 3
			a1 *= 2
			ans[1] -= 1
		while a1 % 2 == 0 and ans[0] > 0:
			a1 //= 2
			ans[0] -= 1
		while b1 % 3 == 0 and ans[1] > 0:
			b1 //= 3
			b1 *= 2
			ans[1] -= 1
		while b1 % 2 == 0 and ans[0] > 0:
			b1 //= 2
			ans[0] -= 1
		while a2 % 3 == 0 and ans[3] > 0:
			a2 //= 3
			a2 *= 2
			ans[3] -= 1
		while a2 % 2 == 0 and ans[2] > 0:
			a2 //= 2
			ans[2] -= 1
		while b2 % 3 == 0 and ans[3] > 0:
			b2 //= 3
			b2 *= 2
			ans[3] -= 1
		while b2 % 2 == 0 and ans[2] > 0:
			b2 //= 2
			ans[2] -= 1
		print(a1, b1)
		print(a2, b2)


(a, b) = map(int, input().split())
(c, d) = map(int, input().split())
e = a * b
f = c * d
n = 0
while e % 2 == 0:
	e = e // 2
while e % 3 == 0:
	e = e // 3
while f % 2 == 0:
	f = f // 2
while f % 3 == 0:
	f = f // 3
if e != f:
	print('-1')
else:
	i = 0
	j = 0
	e = a * b
	f = c * d
	while e % 3 == 0:
		e = e // 3
		i += 1
	while f % 3 == 0:
		f = f // 3
		j += 1
	k = i - j
	if k > 0:
		for i in range(k):
			n += 1
			if a % 3 == 0:
				a = a * 2 // 3
			else:
				b = b * 2 // 3
	else:
		for i in range(0 - k):
			n += 1
			if c % 3 == 0:
				c = c * 2 // 3
			else:
				d = d * 2 // 3
	e = a * b
	f = c * d
	i = 0
	j = 0
	while e % 2 == 0:
		e = e // 2
		i += 1
	while f % 2 == 0:
		f = f // 2
		j += 1
	k = i - j
	if k > 0:
		for i in range(k):
			n += 1
			if a % 2 == 0:
				a = a // 2
			else:
				b = b // 2
	else:
		for i in range(0 - k):
			n += 1
			if c % 2 == 0:
				c = c // 2
			else:
				d = d // 2
	print(n)
	print(a, b)
	print(c, d)


a = [[0] * 2] * 2
s = [[[0] * 2, [0] * 2], [[0] * 2, [0] * 2]]
for i in range(2):
	a[i] = list(map(int, input().split()))
for i in range(2):
	for prime in range(2, 4):
		for j in range(2):
			t = a[i][j]
			while t % prime == 0:
				t //= prime
				s[i][prime - 2][j] += 1
ans = 0
for i in range(2):
	for prime in range(1, 2):
		mi = min(s[0][prime][0] + s[0][prime][1], s[1][prime][0] + s[1][prime][1])
		j = 0
		while s[i][prime][0] + s[i][prime][1] > mi:
			if s[i][prime][j] == 0:
				j += 1
			a[i][j] //= prime + 2
			a[i][j] *= 2
			s[i][0][j] += 1
			s[i][prime][j] -= 1
			ans += 1
for i in range(2):
	for prime in range(1):
		mi = min(s[0][prime][0] + s[0][prime][1], s[1][prime][0] + s[1][prime][1])
		j = 0
		while s[i][prime][0] + s[i][prime][1] > mi:
			if s[i][prime][j] == 0:
				j += 1
			a[i][j] //= prime + 2
			s[i][prime][j] -= 1
			ans += 1
if a[0][0] * a[0][1] != a[1][0] * a[1][1]:
	print(-1)
else:
	print(ans)
	print(a[0][0], a[0][1])
	print(a[1][0], a[1][1])


def follow(x, its=0):
	yield (x, its)
	while x % 2 == 0:
		its += 1
		x //= 2
		yield (x, its)

def segment(x, its=0):
	yield from follow(x, its=its)
	while x % 3 == 0:
		its += 1
		x = x // 3 * 2
		yield from follow(x, its=its)

def joinseg(a, b):
	for (v1, c1) in a:
		for (v2, c2) in b:
			yield (v1 * v2, (c1 + c2, v1, v2))

def best(it, dic):
	return min((dic[x] for x in it))
bar1 = dict(joinseg(*map(lambda x: list(segment(int(x))), input().split(' '))))
bar2 = dict(joinseg(*map(lambda x: list(segment(int(x))), input().split(' '))))
keys = bar1.keys() & bar2.keys()
if not keys:
	print(-1)
else:
	(vals, v1, v2) = zip(best(keys, bar1), best(keys, bar2))
	(b1v, b2v) = zip(v1, v2)
	print(sum(vals))
	print(*b1v)
	print(*b2v)


import sys
size = [0, 0, 0, 0]
(size[0], size[1]) = sys.stdin.readline().strip().split()
(size[2], size[3]) = sys.stdin.readline().strip().split()
for i in range(4):
	size[i] = int(size[i])
totalsize = [size[0] * size[1], size[2] * size[3]]
num = [0, 0, 0, 0, 0, 0, 0, 0]
base = [size[0], size[1], size[2], size[3]]
for i in range(4):
	temp = size[i]
	while temp % 2 == 0:
		num[i * 2] += 1
		temp /= 2
for i in range(4):
	temp = size[i]
	while temp % 3 == 0:
		num[i * 2 + 1] += 1
		temp /= 3
for i in range(4):
	base[i] /= pow(2, num[2 * i])
	base[i] /= pow(3, num[2 * i + 1])
total = 0
if float(totalsize[0]) / pow(2, num[0] + num[2]) / pow(3, num[1] + num[3]) == float(totalsize[1]) / pow(2, num[4] + num[6]) / pow(3, num[5] + num[7]):
	wh = 0
	if num[5] + num[7] > num[1] + num[3]:
		wh = 1
	while num[wh * 4 + 1] + num[wh * 4 + 3] > num[(wh + 1) % 2 * 4 + 1] + num[(wh + 1) % 2 * 4 + 3]:
		if num[wh * 4 + 1] > 0:
			num[wh * 4 + 1] -= 1
			num[wh * 4] += 1
		else:
			num[wh * 4 + 3] -= 1
			num[wh * 4 + 2] += 1
		total += 1
	wh = 0
	if num[4] + num[6] > num[0] + num[2]:
		wh = 1
	while num[wh * 4] + num[wh * 4 + 2] > num[(wh + 1) % 2 * 4] + num[(wh + 1) % 2 * 4 + 2]:
		if num[wh * 4] > 0:
			num[wh * 4] -= 1
		else:
			num[wh * 4 + 2] -= 1
		total += 1
	print(total)
	print(int(base[0] * pow(2, num[0]) * pow(3, num[1])), int(base[1] * pow(2, num[2]) * pow(3, num[3])))
	print(int(base[2] * pow(2, num[4]) * pow(3, num[5])), int(base[3] * pow(2, num[6]) * pow(3, num[7])))
else:
	print(-1)


f = lambda : map(int, input().split())
(a, b) = f()
(c, d) = f()
g = lambda k: 0 if k % p else 1 + g(k // p)
k = 0
for p in (3, 2):
	s = g(a) + g(b) - g(c) - g(d)
	q = p - 1
	for i in range(abs(s)):
		k += 1
		if s > 0:
			if g(a):
				a = a * q // p
			else:
				b = b * q // p
		elif g(c):
			c = c * q // p
		else:
			d = d * q // p
if a * b != c * d:
	print(-1)
else:
	print(k, a, b, c, d)


import sys
(a1, b1) = map(int, input().split())
(a2, b2) = map(int, input().split())
(a, b) = (a1 * b1, a2 * b2)
(cnta2, cntb2, cnta3, cntb3) = (0, 0, 0, 0)
ans = 0
while a % 2 == 0:
	a //= 2
	cnta2 += 1
while a % 3 == 0:
	a //= 3
	cnta3 += 1
while b % 2 == 0:
	b //= 2
	cntb2 += 1
while b % 3 == 0:
	b //= 3
	cntb3 += 1
if a != b:
	print(-1)
	sys.exit()
dif = cnta3 - cntb3
if dif > 0:
	for i in range(dif):
		ans += 1
		if a1 % 3 == 0:
			a1 = a1 * 2 // 3
		else:
			b1 = b1 * 2 // 3
else:
	for i in range(-dif):
		ans += 1
		if a2 % 3 == 0:
			a2 = a2 * 2 // 3
		else:
			b2 = b2 * 2 // 3
(a, b) = (a1 * b1, a2 * b2)
(cnta, cntb) = (0, 0)
while a % 2 == 0:
	a = a // 2
	cnta += 1
while b % 2 == 0:
	b = b // 2
	cntb += 1
dif = cnta - cntb
if dif > 0:
	for i in range(dif):
		ans += 1
		if a1 % 2 == 0:
			a1 = a1 // 2
		else:
			b1 = b1 // 2
else:
	for i in range(-dif):
		ans += 1
		if a2 % 2 == 0:
			a2 = a2 // 2
		else:
			b2 = b2 // 2
print(ans)
print(str(a1) + ' ' + str(b1))
print(str(a2) + ' ' + str(b2))


__author__ = 'zhan'
[a1, b1] = [int(i) for i in input().split()]
[a2, b2] = [int(i) for i in input().split()]
q = [[[a1, b1, 0]], [[a2, b2, 0]]]
total = [0, 0]
tested = [[], []]

def expand(i):
	if not q[i][0][0] & 1:
		tt = [q[i][0][0] // 2, q[i][0][1], q[i][0][2] + 1]
		if not tt[0] * tt[1] in tested[i]:
			q[i].append(tt)
			tested[i].append(tt[0] * tt[1])
	if q[i][0][0] % 3 == 0:
		tt = [q[i][0][0] // 3 * 2, q[i][0][1], q[i][0][2] + 1]
		if not tt[0] * tt[1] in tested[i]:
			q[i].append(tt)
			tested[i].append(tt[0] * tt[1])
	if not q[i][0][1] & 1:
		tt = [q[i][0][0], q[i][0][1] // 2, q[i][0][2] + 1]
		if not tt[0] * tt[1] in tested[i]:
			q[i].append(tt)
			tested[i].append(tt[0] * tt[1])
	if q[i][0][1] % 3 == 0:
		tt = [q[i][0][0], q[i][0][1] // 3 * 2, q[i][0][2] + 1]
		if not tt[0] * tt[1] in tested[i]:
			q[i].append(tt)
			tested[i].append(tt[0] * tt[1])
	q[i].pop(0)
	q[i].sort(key=lambda x: x[0] * x[1], reverse=True)
while True:
	if len(q[0]) > 0 and len(q[1]) > 0:
		total[0] = q[0][0][0] * q[0][0][1]
		total[1] = q[1][0][0] * q[1][0][1]
		if total[0] > total[1]:
			expand(0)
		elif total[0] < total[1]:
			expand(1)
		else:
			print(str(q[0][0][2] + q[1][0][2]) + '\n' + str(q[0][0][0]) + ' ' + str(q[0][0][1]) + '\n' + str(q[1][0][0]) + ' ' + str(q[1][0][1]))
			break
	else:
		print(-1)
		break


__author__ = 'zhan'
[a1, b1] = [int(i) for i in input().split()]
[a2, b2] = [int(i) for i in input().split()]
q1 = [[a1, b1, 0]]
q2 = [[a2, b2, 0]]
tested_total1 = []
tested_total2 = []

def equal(t, q):
	lo = 0
	hi = len(q)
	while True:
		if lo >= hi:
			return False
		m = (lo + hi) // 2
		p = q[m]
		temp = p[0] * p[1]
		if t == temp:
			return [p[0], p[1], p[2]]
		if t < temp:
			lo = m + 1
		elif t > temp:
			hi = m
while True:
	if len(q1) > 0 and len(q2) > 0:
		total1 = q1[0][0] * q1[0][1]
		total2 = q2[0][0] * q2[0][1]
		if total1 > total2:
			ans = equal(total1, q2)
			if ans:
				print(str(ans[2] + q1[0][2]) + '\n' + str(q1[0][0]) + ' ' + str(q1[0][1]) + '\n' + str(ans[0]) + ' ' + str(ans[1]))
			else:
				if not q1[0][0] & 1:
					tt = [q1[0][0] // 2, q1[0][1], q1[0][2] + 1]
					if not tt[0] * tt[1] in tested_total1:
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
				if q1[0][0] % 3 == 0:
					tt = [q1[0][0] // 3 * 2, q1[0][1], q1[0][2] + 1]
					if not tt[0] * tt[1] in tested_total1:
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
				if not q1[0][1] & 1:
					tt = [q1[0][0], q1[0][1] // 2, q1[0][2] + 1]
					if not tt[0] * tt[1] in tested_total1:
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
				if q1[0][1] % 3 == 0:
					tt = [q1[0][0], q1[0][1] // 3 * 2, q1[0][2] + 1]
					if not tt[0] * tt[1] in tested_total1:
						q1.append(tt)
						tested_total1.append(tt[0] * tt[1])
				q1.pop(0)
				q1.sort(key=lambda x: x[0] * x[1], reverse=True)
		elif total1 < total2:
			ans = equal(total2, q1)
			if ans:
				print(str(ans[2] + q2[0][2]) + '\n' + str(ans[0]) + ' ' + str(ans[1]) + '\n' + str(q2[0][0]) + ' ' + str(q2[0][1]))
				break
			else:
				if not q2[0][0] & 1:
					tt = [q2[0][0] // 2, q2[0][1], q2[0][2] + 1]
					if not tt[0] * tt[1] in tested_total2:
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
				if q2[0][0] % 3 == 0:
					tt = [q2[0][0] // 3 * 2, q2[0][1], q2[0][2] + 1]
					if not tt[0] * tt[1] in tested_total2:
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
				if not q2[0][1] & 1:
					tt = [q2[0][0], q2[0][1] // 2, q2[0][2] + 1]
					if not tt[0] * tt[1] in tested_total2:
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
				if q2[0][1] % 3 == 0:
					tt = [q2[0][0], q2[0][1] // 3 * 2, q2[0][2] + 1]
					if not tt[0] * tt[1] in tested_total2:
						q2.append(tt)
						tested_total2.append(tt[0] * tt[1])
				q2.pop(0)
				q2.sort(key=lambda x: x[0] * x[1], reverse=True)
		else:
			print(str(q1[0][2] + q2[0][2]) + '\n' + str(q1[0][0]) + ' ' + str(q1[0][1]) + '\n' + str(q2[0][0]) + ' ' + str(q2[0][1]))
			break
	else:
		print(-1)
		break