Alice and Bob decided to eat some fruit. In the kitchen they found a large bag of oranges and apples. Alice immediately took an orange for herself, Bob took an apple. To make the process of sharing the remaining fruit more fun, the friends decided to play a game. They put multiple cards and on each one they wrote a letter, either 'A', or the letter 'B'. Then they began to remove the cards one by one from left to right, every time they removed a card with the letter 'A', Alice gave Bob all the fruits she had at that moment and took out of the bag as many apples and as many oranges as she had before. Thus the number of oranges and apples Alice had, did not change. If the card had written letter 'B', then Bob did the same, that is, he gave Alice all the fruit that he had, and took from the bag the same set of fruit. After the last card way removed, all the fruit in the bag were over.

You know how many oranges and apples was in the bag at first. Your task is to find any sequence of cards that Alice and Bob could have played with.


-----Input-----

The first line of the input contains two integers, x, y (1 ≤ x, y ≤ 10^18, xy > 1) — the number of oranges and apples that were initially in the bag.


-----Output-----

Print any sequence of cards that would meet the problem conditions as a compressed string of characters 'A' and 'B. That means that you need to replace the segments of identical consecutive characters by the number of repetitions of the characters and the actual character. For example, string AAABAABBB should be replaced by string 3A1B2A3B, but cannot be replaced by 2A1A1B2A3B or by 3AB2A3B. See the samples for clarifications of the output format. The string that you print should consist of at most 10^6 characters. It is guaranteed that if the answer exists, its compressed representation exists, consisting of at most 10^6 characters. If there are several possible answers, you are allowed to print any of them.

If the sequence of cards that meet the problem statement does not not exist, print a single word Impossible.


-----Examples-----
Input
1 4

Output
3B

Input
2 2

Output
Impossible

Input
3 2

Output
1A1B



-----Note-----

In the first sample, if the row contained three cards with letter 'B', then Bob should give one apple to Alice three times. So, in the end of the game Alice has one orange and three apples, and Bob has one apple, in total it is one orange and four apples.

In second sample, there is no answer since one card is not enough for game to finish, and two cards will produce at least three apples or three oranges.

In the third sample, cards contain letters 'AB', so after removing the first card Bob has one orange and one apple, and after removal of second card Alice has two oranges and one apple. So, in total it is three oranges and two apples.

Difficulty: VERY_HARD
Tags: Number theory

Starter code:

Solutions:
def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def solve(x, y, a, b):
	ans = ''
	while not x == 1 or not y == 1:
		if x < y:
			(x, y, a, b) = (y, x, b, a)
		ans += str((x - 1) // y) + a
		x = x - (x - 1) // y * y
	print(ans)
(x, y) = map(int, input().split())
if gcd(x, y) > 1:
	print('Impossible')
else:
	solve(x, y, 'A', 'B')


def gcd(a, b):
	return gcd(b, a % b) if b else a
while 1:
	try:
		(x, y) = map(int, input().split())
	except:
		break
	if gcd(x, y) != 1:
		print('Impossible')
		continue
	res = ''
	while x > 0 and y > 0:
		if x > y:
			(cnt, give) = (x // y, 'A')
			x %= y
		else:
			(cnt, give) = (y // x, 'B')
			y %= x
		if x == 0 or y == 0:
			cnt -= 1
		res += str(cnt) + give
	print(res)


import fractions

def solve(x, y):
	if fractions.gcd(x, y) > 1:
		return 'Impossible'
	turn = x > y
	if not turn:
		(x, y) = (y, x)
	ans = []
	while x != 0 and y != 0:
		ans.append((x // y, 'A' if turn else 'B'))
		(x, y) = (y, x % y)
		turn = not turn
	ans[-1] = (ans[-1][0] - 1, ans[-1][1])
	return ''.join((str(n) + l for (n, l) in ans))
(x, y) = [int(x) for x in input().split()]
print(solve(x, y))


from math import gcd

def help():
	ans = []
	(a, b) = map(int, input().split(' '))
	if gcd(a, b) > 1:
		print('Impossible')
		return
	while a != 1 or b != 1:
		if a == 1:
			ans.append(str(b - 1) + 'B')
			break
		elif b == 1:
			ans.append(str(a - 1) + 'A')
			break
		elif a > b:
			ans.append(str(a // b) + 'A')
			a = a % b
		elif b > a:
			ans.append(str(b // a) + 'B')
			b = b % a
	print(*ans[:], sep='')
help()


def gcd(x, y):
	if x > y:
		(x, y) = (y, x)
	if x == 0:
		return y
	return gcd(y % x, x)
(A, B) = map(int, input().split())

def solve(X, Y):
	if X > Y:
		if Y == 1:
			print(str(X - 1) + 'A', end='')
			return
		else:
			print(str(X // Y) + 'A', end='')
			solve(X % Y, Y)
	elif X == 1:
		print(str(Y - 1) + 'B', end='')
		return
	else:
		print(str(Y // X) + 'B', end='')
		solve(X, Y % X)
if gcd(A, B) == 1:
	solve(A, B)
else:
	print('Impossible')


def solve(a, b):
	r = []
	while a and b and (a + b > 2):
		q = min(a // b + b // a, max(a, b) - 1)
		r.append(str(q))
		if a > b:
			r.append('A')
			a -= b * q
		else:
			r.append('B')
			b -= a * q
	if a != 1 or b != 1:
		return 'Impossible'
	return ''.join(r)

def main():
	(a, b) = map(int, input().split())
	print(solve(a, b))
main()


def gcd(m, n):
	if m < n:
		(m, n) = (n, m)
	r = m % n
	while r:
		(m, n) = (n, r)
		r = m % n
	return n

def search(x, y):
	nonlocal ans
	while True:
		if x == 1:
			ans = ans + ('' if y == 1 else str(y - 1) + 'B')
			return
		if y == 1:
			ans = ans + ('' if x == 1 else str(x - 1) + 'A')
			return
		if x < y:
			ans = ans + str(y // x) + 'B'
			(x, y) = (x, y % x)
		else:
			ans = ans + str(x // y) + 'A'
			(x, y) = (x % y, y)
(a, b) = [int(i) for i in input().split()]
if gcd(a, b) != 1:
	print('Impossible')
else:
	ans = ''
	search(a, b)
	print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

class fraction:
	(n, m) = (0, 0)

	def __init__(self, n, m):
		d = int(gcd(n, m))
		self.n = int(n // d)
		self.m = int(m // d)

	def add(self, tmp):
		return fraction(self.n * tmp.m, self.m * tmp.n)

	def compareTo(self, tmp):
		a = self.n * tmp.m
		b = self.m * tmp.n
		if a > b:
			return 1
		elif a < b:
			return -1
		return 0

	def sternBrocotAdd(self, tmp):
		return fraction(self.n + tmp.n, self.m + tmp.m)

def run(left, right, result):
	a = left.n
	b = left.m
	p = right.n
	q = right.m
	n = result.n
	m = result.m
	mid = left.sternBrocotAdd(right)
	if mid.compareTo(result) == 0:
		return
	ch = 'Z'
	x = 0
	if mid.compareTo(result) <= 0:
		x = int((b * n - a * m) // (p * m - q * n))
		left = fraction(a + p * x, b + q * x)
		ch = 'A'
		if left.compareTo(result) == 0:
			x -= 1
	else:
		x = int((p * m - q * n) // (b * n - a * m))
		right = fraction(a * x + p, b * x + q)
		ch = 'B'
		if right.compareTo(result) == 0:
			x -= 1
	s = str.format('%d%c' % (x, ch))
	print(s, end='')
	if left.compareTo(result) == 0 or right.compareTo(result) == 0:
		return
	run(left, right, result)
(p, q) = map(int, input().split())
d = gcd(p, q)
if d == 1:
	result = fraction(p, q)
	right = fraction(1, 0)
	left = fraction(0, 1)
	run(left, right, result)
else:
	print('Impossible')


a = input().split()
target = (int(a[0]), int(a[1]))
x = (1, 0)
y = (0, 1)
toadd = 'A'
ans = ''

def less(a, b):
	return a[0] * b[1] < b[0] * a[1]
while True:
	z = (x[0] + y[0], x[1] + y[1])
	if z[0] > target[0] or z[1] > target[1]:
		print('Impossible')
		exit()
	if z == target:
		print(ans)
		exit()
	if less(z, target):
		low = 1
		high = int(1e+18)
		while high > low:
			guess = (low + high + 1) // 2
			if less((x[0] * guess + y[0], x[1] * guess + y[1]), target):
				low = guess
			else:
				high = guess - 1
		ans += str(low)
		ans += 'A'
		y = (y[0] + low * x[0], y[1] + low * x[1])
	elif less(target, z):
		low = 1
		high = int(1e+18)
		while high > low:
			guess = (low + high + 1) // 2
			if less(target, (x[0] + guess * y[0], x[1] + guess * y[1])):
				low = guess
			else:
				high = guess - 1
		ans += str(low)
		ans += 'B'
		x = (x[0] + low * y[0], x[1] + low * y[1])
	else:
		print('Impossible')
		exit()


(x, y) = (int(w) for w in input().split())
(ax, ay) = (1, 0)
(bx, by) = (0, 1)
anext = x > y
ch = 'AB' if x > y else 'BA'
ans = []
while ax + ay + bx + by < x + y:
	if anext:
		n = 0
		for sh in range(59, -1, -1):
			t = n + (1 << sh)
			if y * (bx + t * ax) < x * (by + t * ay):
				n = t
		if not n:
			print('Impossible')
			exit(0)
		ans.append(n)
		bx = bx + n * ax
		by = by + n * ay
	else:
		n = 0
		for sh in range(59, -1, -1):
			t = n + (1 << sh)
			if y * (ax + t * bx) > x * (ay + t * by):
				n = t
		if not n:
			print('Impossible')
			exit(0)
		ans.append(n)
		ax = ax + n * bx
		ay = ay + n * by
	anext = not anext
for (i, a) in enumerate(ans):
	print('%d%s' % (a, ch[i & 1]), end='')
print()


import sys
read = lambda : list(map(int, sys.stdin.readline().split()))
(x, y) = read()
res = []
c = 'A'
while x * y > 1:
	k = min(x // y, x - 1)
	if k > 0:
		res.append('{}{}'.format(k, c))
	(x, y) = (y, x - k * y)
	c = 'A' if c == 'B' else 'B'
if x == 0 or y == 0:
	print('Impossible')
else:
	print(''.join(res))


def f(x, y):
	m = x
	n = y
	s = ''
	while m != 0 and n != 0:
		if m >= n:
			r = m // n
			m = m % n
			c = 'A'
		else:
			r = n // m
			n = n % m
			c = 'B'
		if m == 0 or n == 0:
			if r > 1:
				s = s + str(r - 1) + c
		else:
			s = s + str(r) + c
	if m + n > 1:
		return 'Impossible'
	else:
		return s
inp = input()
[x, y] = [int(t) for t in inp.split(' ')]
print(f(x, y))


def gcd(a, b):
	if b == 0:
		return a
	if a // b != 0:
		l.append(a // b)
	return gcd(b, a % b)
l = []
t = ['A', 'B']
(x, y) = list(map(int, input().split()))
g = gcd(x, y)
l[-1] -= 1
if g == 1:
	if x > y:
		start = 0
	else:
		start = 1
	s = ''
	for v in range(len(l)):
		s += str(l[v]) + t[(start + v) % 2]
	print(s)
else:
	print('Impossible')


from operator import gt, lt
(x, y) = (int(w) for w in input().split())
if x > y:
	ch = 'AB'
	(op1, op2) = (lt, gt)
	(ax, ay, bx, by) = (1, 0, 0, 1)
else:
	ch = 'BA'
	(op1, op2) = (gt, lt)
	(ax, ay, bx, by) = (0, 1, 1, 0)
ans = []
while ax + ay + bx + by < x + y:
	n = 0
	for sh in range(59, -1, -1):
		t = n + (1 << sh)
		if op1(y * (bx + t * ax), x * (by + t * ay)):
			n = t
	if not n:
		print('Impossible')
		exit(0)
	ans.append(n)
	(ax, bx) = (bx + n * ax, ax)
	(ay, by) = (by + n * ay, ay)
	(op1, op2) = (op2, op1)
for (i, a) in enumerate(ans):
	print('%d%s' % (a, ch[i & 1]), end='')
print()


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
(x, y) = map(int, input().split())
if gcd(x, y) != 1:
	print('Impossible')
	return
a = []
while y != 1:
	a += [x // y]
	x %= y
	(x, y) = (y, x)
a += [x - 1]
s = 'A'
for x in a:
	if x > 0:
		print(x, end=s)
	s = 'AB'.replace(s, '')


def gcd(x, y):
	while y > 0:
		(x, y) = (y, x % y)
	return x
(x, y) = map(int, input().split())
if gcd(x, y) != 1:
	print('Impossible')
	exit(0)
res = ''
while x > 0 and y > 0:
	if y > x:
		if x == 1:
			y -= 1
		res = res + str(y // x) + 'B'
		y = y % x
	else:
		if y == 1:
			x -= 1
		res = res + str(x // y) + 'A'
		x = x % y
print(res)


(x, y) = map(int, input().split(' '))
res = []
c = 'A'
while x * y > 1:
	k = min(x // y, x - 1)
	if k > 0:
		res.append('{}{}'.format(k, c))
	(x, y) = (y, x - k * y)
	c = 'A' if c == 'B' else 'B'
if x == 0 or y == 0:
	print('Impossible')
else:
	print(''.join(res))


def gcd(m, n):
	if m < n:
		(m, n) = (n, m)
	r = m % n
	while r:
		(m, n) = (n, r)
		r = m % n
	return n

def search(x, y):
	while True:
		if x == 1:
			ans.extend([] if y == 1 else str(y - 1) + 'B')
			return
		if y == 1:
			ans.extend([] if x == 1 else str(x - 1) + 'A')
			return
		if x < y:
			ans.append(str(y // x) + 'B')
			(x, y) = (x, y % x)
		else:
			ans.append(str(x // y) + 'A')
			(x, y) = (x % y, y)
(a, b) = [int(i) for i in input().split()]
if gcd(a, b) != 1:
	print('Impossible')
else:
	ans = []
	search(a, b)
	(i, length) = (0, len(ans))
	print(''.join(ans))