Given a binary number $S$ containing only of 1's and 0's, find two binary numbers $A$ and $B$ such that the sum of the number of 1's in $A$ and $B$ is minimum and $A-B=S$. If there are many such numbers, you can print any.

The binary number $S$ has some properties. See the Constraints section for details.

------ Input: ------

The only line of input contains a single binary number $S$ without leading zeroes. 

------ Output: ------
Print two numbers $A$ and $B$ in one line without leading zeroes. If any number is zero, just print $0$.

------ Constraints  ------
$2 ≤$ number of bits in $S ≤ 10^{6}$
The string $S$ has at least 1 one and 1 zero and has exactly two parts: all 1's followed by all 0's.

----- Sample Input 1 ------ 
1110000
----- Sample Output 1 ------ 
10000000 10000
----- explanation 1 ------ 
1110000 is 112 in decimal.

10000000 is 128 in decimal. 10000 is 16 in decimal. 128 - 16 = 112. Hence the given output is valid. The sum of the number of 1's in $A$ and $B$ is 1 + 1 = 2. You can check that this cannot be decreased. Hence this is a correct answer.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
s = str(input().strip())
if s.count('1') == 1:
	print(s, '0')
else:
	print('1' + '0' * len(s), '1' + '0' * s.count('0'))


import sys
s = str(input().strip())
if s.count('1') == 1:
	print(s, '0')
else:
	print('1' + '0' * len(s), '1' + '0' * s.count('0'))


s = input()
if s.count('1') == 1:
	print(s, '0')
else:
	print('1' + '0' * len(s), '1' + '0' * s.count('0'))


s = str(input())
o = s.count('1')
z = s.count('0')
l = o + z
if o == 1:
	print(s, 0)
else:
	a = '1'
	a += l * '0'
	b = '1' + z * '0'
	print(a, b)


s = str(input())
ones = s.count('1')
zeroes = s.count('0')
l = ones + zeroes
if ones == 1:
	print(s, 0)
else:
	big = '1'
	big += l * '0'
	small = '1' + zeroes * '0'
	print(big, small)


s = input().strip()
one = s.count('1')
zero = s.count('0')
if one == 1:
	print(s, 0)
else:
	print('1' + '0' * len(s), '1' + '0' * zero)


s = input()
l = len(s)
ll = s.count('1')
if ll == 1:
	print(s, 0)
else:
	a = '1' + '0' * l
	b = '1' + '0' * (l - ll)
	print(a, b)


s = input()
z = 0
o = 0
for i in s:
	if i == str(0):
		z += 1
	if i == str(1):
		o += 1
if o == 1:
	print(s, ' 0')
else:
	print(10 ** (z + o), ' ', 10 ** z)


s = input()
if s.count('1') == 1:
	print(s, '0')
else:
	n1 = bin(2 ** len(s))
	n2 = bin(2 ** s.count('0'))
	print(n1[2:], n2[2:])


s = input()
c1 = s.count('1')
c0 = s.count('0')
a = '1' + '0' * len(s)
b = '1' + '0' * c0
if c1 == 1:
	print(s, '0')
else:
	print(a, b)


s = input()
if s[1] == '0':
	print(s + ' 0')
	exit(0)
print('1' + '0' * len(s), end=' ')
ind = s.find('0')
print('1' + (len(s) - ind) * '0')


def nextPowerOf2(n):
	p = 1
	if n and (not n & n - 1):
		return n
	while p < n:
		p <<= 1
	return p
st = int(input(), 2)
n = nextPowerOf2(st)
diff = n - st
print(bin(n)[2:], bin(diff)[2:])


s = input()
k = 0
u = len(s)
for i in range(u):
	if s[i] == '1':
		k += 1
	else:
		break
if k == 1:
	print(s, end=' ')
	print(0)
else:
	t = pow(2, u)
	y = bin(t)[2:]
	print(y, end=' ')
	pa = pow(2, k)
	g = t // pa
	h = bin(g)[2:]
	print(h)


p = input().strip()
if p[1] == '0':
	print(p, 0)
else:
	a = '1'
	b = '1'
	flag = False
	for c in p:
		if c == '0' and (not flag):
			flag = True
		if flag:
			b += '0'
		a += '0'
	print(a, b)


t = input()
one = t.count('1')
r = len(t)
num1 = int('1' + '0' * r)
num2 = int('1' + '0' * (r - one))
if one == 1:
	print(int(t), 0)
else:
	print(num1, num2)


def isPower(x):
	return x and (not x & x - 1)
s = input()
val = int(s, 2)
a = len(s)
b = s.count('0')
if isPower(val):
	s1 = s
	s2 = '0'
	print(s1 + ' ' + s2)
else:
	s1 = '1' + '0' * a
	s2 = '1' + '0' * b
	print(s1 + ' ' + s2)


s = input()
k = 0
for i in s:
	if i == '1':
		k = k + 1
if k > 1:
	a = '1' + '0' * len(s)
	b = '1' + '0' * (len(s) - k)
else:
	a = s
	b = '0'
print(a, b)


s = input()
count = 0
for i in range(0, len(s)):
	if s[i] == '0':
		break
	else:
		count += 1
b = int('1' + '0' * (len(s) - count), 2)
a = int(s, 2) + b
if bin(b)[2:] == s:
	print(bin(b)[2:], 0)
else:
	print(bin(a)[2:], bin(b)[2:])


s = input()
length = len(s)
one = 0
for i in range(length):
	if s[i] == '1':
		one += 1
	else:
		break
if one == 1:
	print(s + ' 0')
else:
	first = '1' + '0' * length
	second = '1' + '0' * (length - one)
	print(first, ' ', second)


s = list(input())
no_of_ones = 0
for i in s:
	if i == '0':
		break
	no_of_ones += 1
if no_of_ones == 1:
	print(''.join(s), 0)
else:
	print('1', end='')
	for i in range(0, len(s)):
		print('0', end='')
	print(' 1', end='')
	for i in range(0, len(s) - no_of_ones):
		print('0', end='')


T = str(input().strip())
lenT = len(T)
oneNum = T.count('1')
zeroCount = lenT - oneNum
if oneNum == 1:
	print(T, '0')
else:
	num1 = '1' + lenT * '0'
	num2 = '1' + zeroCount * '0'
	print(num1, num2)


a = input().strip()
if a.count('1') == 1:
	print(a + ' ' + '0')
else:
	x = 2 ** len(a)
	y = 2 ** a.count('0')
	print(str(bin(x)[2:]) + ' ' + str(bin(y)[2:]))


n = input()
l = ''
f = 0
j = list(n)
t = j.index('1')
if t == 0 and j.count('1') == 1:
	print(n, '0')
else:
	for i in range(len(n) - 1, -1, -1):
		if n[i] == '0':
			l += n[i]
		elif n[i] == '1':
			l += n[i]
			f = 1
		if f == 1:
			break
	k = l[::-1]
	s = ''
	for i in range(len(k)):
		s += k[i]
	c = int(s, 2)
	co = c + int(n, 2)
	k1 = bin(co)
	print(k1[2:len(k1)], k)


S = input()
nz = S.count('0')
B = '1' + '0' * nz
if B == S:
	print(B, '0')
else:
	s = int(S, 2)
	b = int(B, 2)
	a = b + s
	A = str(bin(a))
	print(A[2:], B)


s = input()
if s.count('1') <= 2:
	print(s, 0)
else:
	l = len(s)
	sss = '1'
	for i in range(l):
		sss += '0'
	ss = '1'
	p = s.index('0')
	for i in range(p, l):
		ss += '0'
	print(sss, ss)


s = input()
x = len(s)
a = pow(10, x)
setbits = 0
for i in s:
	if i == '0':
		break
	setbits = setbits + 1
b = pow(10, x - setbits)
if setbits > 1:
	print(a, b)
else:
	print(s, 0)


s = input()
n = len(s)
zero = s.count('0')
one = s.count('1')
if one == 1:
	print(s, end=' ')
	print(0)
else:
	print(1, end='')
	for i in range(n):
		print(0, end='')
	print(' ', end='')
	print(1, end='')
	for i in range(zero):
		print(0, end='')


s = input()
a = 1 << len(s) if int(s[1:]) != 0 else int(s, 2)
print('{0:b} {1:b}'.format(a, a - int(s, 2)))


S = input()
c0 = S.count('0')
c1 = S.count('1')
if c1 == 1:
	print(S, 0)
else:
	print('1' + '0' * len(S), '1' + '0' * c0)


N = input()
if N[0] != N[1]:
	print(N, end=' ')
	print('0')
else:
	print('1', end='')
	j = 0
	for i in range(len(N)):
		if N[i] == '1':
			j = i
		print('0', end='')
	print(' 1', end='')
	for i in range(j + 1, len(N)):
		print('0', end='')


def next_power_of_2(x):
	return 1 if x == 0 else 2 ** (x - 1).bit_length()
a = int(input(), 2)
b = next_power_of_2(a)
c = b - a
print(bin(b)[2:], ' ', bin(c)[2:])


s = input()
for i in range(len(s) - 1, -1, -1):
	if s[i] == '1':
		j = i
		break
if j == 0:
	print(s, '0')
else:
	h = s[j:]
	re = int(s, 2)
	rt = int(h, 2)
	r = bin(re + rt)
	print(bin(re + rt)[2:], bin(rt)[2:])


s = input()
if s[0] == '1' and s[1] == '0':
	a = s
	b = '0'
else:
	for i in range(len(s)):
		if s[i] == '1' and s[i + 1] == '0':
			b = s[i:]
	a = '1' + len(s) * '0'
print(a + ' ' + b)


S = input()
if S.count('1') == 1:
	print(S, '0')
	exit()
print('1', end='')
print('0' * len(S), end=' ')
print('1', end='')
print('0' * S.count('0'))


s = input()
n = int(s, 2)
l = len(s)
s1 = '1' + '0' * l
n1 = int(s1, 2)
p = n1 - n
b = bin(p)
b = b[2:]
pp = b.count('1')
if pp + 1 < s.count('1'):
	print(s1, b)
else:
	print(s, 0)


s = input()
n = len(s)
if s.count('1') == 1:
	print(s, 0)
else:
	zero = s.count('0')
	a = '1' + '0' * n
	b = '1' + '0' * zero
	print(a, b)