You are given a ternary string (it is a string which consists only of characters '0', '1' and '2').

You can swap any two adjacent (consecutive) characters '0' and '1' (i.e. replace "01" with "10" or vice versa) or any two adjacent (consecutive) characters '1' and '2' (i.e. replace "12" with "21" or vice versa).

For example, for string "010210" we can perform the following moves:   "010210" $\rightarrow$ "100210";  "010210" $\rightarrow$ "001210";  "010210" $\rightarrow$ "010120";  "010210" $\rightarrow$ "010201". 

Note than you cannot swap "02" $\rightarrow$ "20" and vice versa. You cannot perform any other operations with the given string excluding described above.

You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (possibly, zero).

String $a$ is lexicographically less than string $b$ (if strings $a$ and $b$ have the same length) if there exists some position $i$ ($1 \le i \le |a|$, where $|s|$ is the length of the string $s$) such that for every $j < i$ holds $a_j = b_j$, and $a_i < b_i$.


-----Input-----

The first line of the input contains the string $s$ consisting only of characters '0', '1' and '2', its length is between $1$ and $10^5$ (inclusive).


-----Output-----

Print a single string — the minimum possible (lexicographically) string you can obtain by using the swaps described above arbitrary number of times (possibly, zero).


-----Examples-----
Input
100210

Output
001120

Input
11222121

Output
11112222

Input
20

Output
20

Difficulty: interview

Starter code:

Solutions:
s = input()
pref = []
cnt1 = s.count('1')
s = s.replace('1', '')
i = 0
while i < len(s) and s[i] != '2':
	i += 1
end = ''
if i != len(s):
	end = s[i:]
s = s[:i] + '1' * cnt1 + end
print(s)

s = input()
ans = []     
cnt1 = 0
for c in s:
  if c == '1':
    cnt1 += 1
  else:
    ans += [c]
j = 0
while j < len(ans) and ans[j] == '0':
  j += 1
ans = ans[:j] + ['1'] * cnt1 + ans[j:]
print(''.join(ans))


a = input()+'2'
f = a.index('2')
b = a[f:]
o = ''
for i in b:
    if i !='1':
        o+=i
a = a[:f]
print(a.count('0')*'0'+a.count('1')*'1'+b.count('1')*'1'+o[:-1])


s = input()
a = ""
s = s[::-1]
o = 0
z = 0
i = 0
while i != len(s):
	if s[i] == '2':
		a = a + '0'*z + '2'
		z = 0
	if s[i] == '0':
		z+=1
	if s[i] == '1':
		o+=1
	i+=1
a = a + '1'*o + '0'*z
a = a[::-1]
print(a)

t = input()
t = t+'2'
Z = []
U = 0
c = 0
for i in t:
    if i=='1':
        U+=1
    elif i=='0':
        c+=1
    else:
        Z.append(c)
        c = 0
for i in range(Z[0]):
    print('0', end='')
for i in range(U):
    print('1', end='')
for j in range(1, len(Z)):
    print('2', end='')
    for i in range(Z[j]):
        print('0', end='')


s=input()
answer=''
p=0
o=1
for i in s:
    if i=='1':
        p=p+1
for i in s:
    if i=='0':
        answer=answer+'0'
    elif i=='2':
        answer=answer+'1'*(o*p)
        o=0
        answer=answer+'2'
answer=answer+'1'*(o*p)
print(answer)

import time
from copy import deepcopy
import itertools
from bisect import bisect_left
from bisect import bisect_right
import math
from collections import deque
from collections import Counter


def read():
    return int(input())


def readmap():
    return map(int, input().split())


def readlist():
    return list(map(int, input().split()))


S = list(map(int, list(input())))
num1 = S.count(1)
for i in range(len(S)):
    if S[i] == 2:
        index = i
        break
    index = len(S)

ans = []
for i in range(len(S)):
    if i == index:
        ans += [1] * num1
    if S[i] != 1:
        ans.append(S[i])

if index == len(S):
    ans += [1] * num1

print("".join(list(map(str, ans))))

def main():
    s = input()
    n = len(s)
    nums = [[], [], []]
    if n == 1:
        print(s)
        return 0
    for i in range(n):
        nums[int(s[i])].append(i)
    if len(nums[0]) == 0:
        temp = len(nums[1])
        print("1" * temp + "2" * (n - temp))
    elif len(nums[2]) == 0:
        temp = len(nums[0])
        print("0" * temp + "1" * (n - temp))
    else:
        S = [i for i in s if i != "1"]
        temp = len(nums[1])
        for i in range(len(S)):
            if S[i] == "2":
                break
        print("".join(S[:i]) + temp * "1" + "".join(S[i:]))
    return 0
main()

s = input()
tmp = ""
s = s[::-1]
xx = z = it = 0
while it < len(s):
	if s[it] == '2':
		tmp = tmp + '0'*z + '2'
		z = 0
	if s[it] == '0':
		z+=1
	if s[it] == '1':
		xx+=1
	it = it + 1
tmp = tmp + '1'*xx + '0'*z
print(tmp[::-1])

s = input()
t = ""
num = 0
for i in range(len(s)):
    if s[i] == "1":
        num += 1
    else:
        t += s[i]
s = num * "1" + t
p = s.split("0")
q = []
for k in p:
    q.append("".join(sorted(list(k))))
p = "0".join(q)

p = p.split("2")
q = []
for k in p:
    q.append("".join(sorted(list(k))))
p = "2".join(q)
print(p)

# from math import ceil

t = 1
for test in range(t):
    n = list(input())
    firstZeros = 0
    onesCount = 0
    for i in n:
        if i=="1":
            onesCount+=1
    index = 0
    for i in n:
        if i=="0":
            firstZeros+=1
        elif i=="2":
            break
        index+=1
    print("0"*firstZeros,end="")
    print("1"*onesCount, end="")
    zeroCount = 0
    for i in range(index, len(n)):
        if n[i]=="2":
            print("0"*zeroCount, end="")
            print("2", end="")
            zeroCount = 0
        elif n[i]=="0":
            zeroCount+=1
    print("0"*zeroCount)

s = input()
s = [int(i) for i in s]
s.reverse()

ans = [0] * len(s)
f = 0

r0, r1 = 0, 0

for i in s:
    if i == 2:
        while r0:
            r0 -= 1
            ans[f] = 0
            f += 1
        ans[f] = 2
        f += 1
    elif i == 1:
        r1 += 1
    else:
        r0 += 1

while r1:
    r1 -= 1
    ans[f] = 1
    f += 1
while r0:
    r0 -= 1
    ans[f] = 0
    f += 1

ans.reverse()
for i in ans:
    print(i, end='')



s = input()
a = s.count('1')
l = []
for i in s:
	if i != '1':
		l.append(i)
b = ['1']*a
c = len(l)
for i in range(len(l)):
	if l[i] == '2':
		c = i
		break
ans = l[0:c] + b + l[c:len(l)]
for i in ans:
	print(str(i), end = '')


s = str(input())

answer = []


ed_count = 0
prev_null = 0

prev_twos = 0
for el in s:
    if el == "1":
        ed_count += 1
    else:
        if el == "0":
            if prev_null == 0:
                if prev_twos!=0:
                    answer.append([2, prev_twos])
                    prev_twos = 0

            prev_null +=1
        else:
            if prev_twos == 0:
                if prev_null!=0:
                    answer.append([0, prev_null])
                    prev_null = 0
                    
            prev_twos +=1
    


if prev_twos!=0:
    answer.append([2, prev_twos])
    prew_twos = 0

if prev_null!=0:
    answer.append([0, prev_null])
    prev_null = 0

if len(answer) !=0 and answer[0][0] == 0:
    print("{}".format(answer[0][0]) * answer[0][1], end = '')

print("1"*ed_count, end = "")
z = len(answer)
min_in = 0
if z!= 0 and answer[0][0] == 0:
    min_in += 1
for i in range(min_in, z):
    print(str(answer[i][0]) * answer[i][1], end = "")
            


s = input()
tmp = ""
s = s[::-1]
xx = z = it = 0
for c in s:
	if c == '2':
		tmp = tmp + '0'*z + '2'
		z = 0
	if c == '0':
		z+=1
	if c == '1':
		xx+=1
	it = it + 1
tmp = tmp + '1'*xx + '0'*z
print(tmp[::-1])

r=list(input())
s=""
count=0
for i in r:
	if i=="1":
		count=count+1
	else:
		s=s+i
ans=""
u=0
while(u<len(s)):
	if s[u]=="2":
		break
	else:
		u=u+1
ans=s[:u]+count*"1"+s[u:]
print (ans)

s = input()
n = len(s)
_0, _1, i = 0, 0, 0
while i < n and s[i] != '2':
  if s[i] == '0': _0 += 1
  elif s[i] == '1': _1 += 1
  i += 1
front = '0'*_0 + '1' * _1
end = ''
for c in s[i:]:
  if c == '1':
    front += c
  else:
    end += c
print(front + end)


s = input()
c0 = c1 = 0
d0 = []
for c in s:
    if c == '0': c0 += 1
    elif c == '1': c1 += 1
    else:
        d0.append(c0)
        c0 = 0
d0.append(c0)
res=[]
for i in range(len(d0)):
    for j in range(d0[i]):
        res.append('0')
    if i == 0:
        for j in range(c1):
            res.append('1')
    if i < len(d0)-1:
        res.append('2')
print(''.join(res))


s = input()
ans = []
ones = 0
for i in s:
    if i != '1':
        ans += [i]
    else :
        ones += 1
i = 0
n = len(ans)
while i < n and ans[i] != '2':
    print(0,end="")
    i += 1
print("1"*ones,end="")

while i < n:
    print(ans[i],end="")
    i+= 1


from sys import stdin
line = stdin.readline().rstrip()


count0 = 0
count1 = 0
index = 0
found2 = False
for c in line:
    index +=1
    if c == '0':
        count0+=1
    if c == '2':
        found2 = True
        break
while count0 > 0:
    count0-=1
    print('0', end='')
for c in line:
    if c == '1':
        print('1', end='')
if found2:
    print('2', end='')
for i in range(index, len(line)):
    if line[i] != '1':
        print(line[i], end='')


def main():
    s = list(map(int, input()))
    cnt0, cnt1 = 0, 0
    ans = []
    for a in s:
        if a == 1:
            cnt1 += 1
        elif a == 2:
            ans.append(a)
        elif a == 0:
            if not ans:
                cnt0 += 1
            else:
                ans.append(a)
    s = '0' * cnt0 + '1' * cnt1 + ''.join(map(str, ans))
    print(s)

def __starting_point():
    main()

__starting_point()

s=input()
l=len(s)
z=-1
c0=0
c1=0
c2=0
loc=-1
for i in range(l):
    c=s[i]
    if c=='0':
        c0+=1
    if c=='1':
        c1+=1
    if c=='2':
        c2+=1
        if z==-1:
            z=c0
            loc=i
if z==-1:# no 2
    for i in range(c0):
        print(0,end='')
    for i in range(c1):
        print(1,end='')
    print()
else:
    for i in range(z):
        print(0, end='')
    for i in range(c1):
        print(1, end='')
    for i in range(loc,l):
        if s[i]!='1':
            print(s[i],end='')
    print()

s = input()
temp = None
paste = None
zero, one = 0,0
for i in range(len(s)):
    if s[i] == '2':
        temp = s[i:]
        break
    elif s[i] == '1':
        one += 1
    elif s[i] == '0':
        zero += 1
if temp is not None:
    for x in temp:
        if x == '1':
            one += 1
    paste = temp.replace("1", "")
ans = '0'*zero + '1'*one
if paste is not None:
    ans += paste
print(ans)


s = input()
t = s.count('1')
s = s.replace('1', '')

i = s.find('2')
if i == -1:
    print(s + '1'*t)
else:
    print(s[:i] + '1'*t + s[i:])