The only difference between easy and hard versions is the length of the string. You can hack this problem only if you solve both problems.

Kirk has a binary string $s$ (a string which consists of zeroes and ones) of length $n$ and he is asking you to find a binary string $t$ of the same length which satisfies the following conditions:



 For any $l$ and $r$ ($1 \leq l \leq r \leq n$) the length of the longest non-decreasing subsequence of the substring $s_{l}s_{l+1} \ldots s_{r}$ is equal to the length of the longest non-decreasing subsequence of the substring $t_{l}t_{l+1} \ldots t_{r}$;

 The number of zeroes in $t$ is the maximum possible.

A non-decreasing subsequence of a string $p$ is a sequence of indices $i_1, i_2, \ldots, i_k$ such that $i_1 < i_2 < \ldots < i_k$ and $p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$. The length of the subsequence is $k$.

If there are multiple substrings which satisfy the conditions, output any.


-----Input-----

The first line contains a binary string of length not more than $2\: 000$.


-----Output-----

Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.


-----Examples-----
Input
110

Output
010

Input
010

Output
010

Input
0001111

Output
0000000

Input
0111001100111011101000

Output
0011001100001011101000



-----Note-----

In the first example: 

 For the substrings of the length $1$ the length of the longest non-decreasing subsequnce is $1$;  For $l = 1, r = 2$ the longest non-decreasing subsequnce of the substring $s_{1}s_{2}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{2}$ is $01$;  For $l = 1, r = 3$ the longest non-decreasing subsequnce of the substring $s_{1}s_{3}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{3}$ is $00$;  For $l = 2, r = 3$ the longest non-decreasing subsequnce of the substring $s_{2}s_{3}$ is $1$ and the longest non-decreasing subsequnce of the substring $t_{2}t_{3}$ is $1$; 

The second example is similar to the first one.

Difficulty: interview

Starter code:

Solutions:
s = list(map(int, input()))
ans = []
cnt = 0
if s[0] == 1:
    cnt += 1
else:
    ans.append('0')
for i in range(1, len(s)):
    if s[i] == 0 and s[i - 1] == 0:
        ans.append('0')
    elif s[i] == 1:
        cnt += 1
    else:
        maba = 0
        b = 0
        for x in range(i, len(s)):
            if s[x] == 1:
                b -= 1
            else:
                b += 1
            maba = max(maba, b)
        maba = min(maba, cnt)
        for _ in range(cnt - maba):
            ans.append('0')
        for _ in range(maba):
            ans.append('1')
        cnt = 0
        ans.append('0')
for _ in range(len(s) - len(ans)):
    ans.append('0')
print(''.join(ans))


def main():
    import sys
    input = sys.stdin.readline
    
    s = [int(i) for i in input()[:-1]][::-1]
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for j in range(n):
        tmp = [0, 0]
        for i in range(j, n):
            if s[i] == 0:
                tmp[0] = max(tmp) + 1
                dp[j][i] = tmp[0]
            else:
                tmp[1] += 1
                dp[j][i] = tmp[1]
    
    t = ""
    dp2 = [[0] * n for _ in range(n)]
    tmp = [[0, 0] for _ in range(n)]
    for j in range(n):
        okay = 1
        prev = [0] * (j + 1)
        for i in range(j + 1):
            prev[i] = tmp[i][0]
            tmp[i][0] = max(tmp[i]) + 1
            dp2[i][j] = tmp[i][0]
            if dp2[i][j] != dp[i][j]:
                okay = 0
        
        if not okay:
            for i in range(j + 1):
                tmp[i][0] = prev[i]
                tmp[i][1] += 1
                dp2[i][j] = tmp[i][1]
            t += '1'
        else:
            t += '0'
    
    print(t[::-1])
    
    return 0

main()

from sys import stdin
s=stdin.readline().strip()
dp=[0 for i in range(len(s)+2)]
ons=[0 for i in range(len(s)+2)]
zs=[0 for i in range(len(s)+2)]
for i in range(len(s)-1,-1,-1):
    if s[i]=="1":
        ons[i]+=1
    if(i!=len(s)-1):
        ons[i]+=ons[i+1]
z=0
for i in range(len(s)-1,-1,-1):
    if(s[i]=="1"):
        dp[i]=max(1+ons[i+1],z)
    else:
        dp[i]=max(dp[i+1]+1,1+ons[i+1])
        z=dp[i]
    zs[i]=z

ans=""    
for i in range(len(s)):
    if s[i]=="1":
        x=dp[i]
        y=1+dp[i+1]
        if x==y:
            ans+="0"
        else:
            ans+="1"
    else:
        ans+="0"
print(ans)


s = input()
n = len(s)
if n == 1:
	print(0)
elif n == 2:
	if s == "10":
		print("10")
	else:
		print("00")
else:
	s_lis = 0
	s_max = 0
	s_zero = 0
	t_zero = 0
	stack_01 = []
	t = []
	for i in range(n):
		t.append("0")
		t_zero += 1
		if s[i] == "0":
			s_zero += 1
		if i > 0 and s[i-1:i+1] == "10":
			t[i-1] = "1"
			t_zero -= 1
			stack_01.append(i-2)
		if s_max <= int(s[i]):
			s_lis += 1
			s_max = max(s_max, int(s[i]))
		if s_lis <= s_zero:
			s_lis = s_zero
			s_max = 0
		if s_lis < t_zero:
			#print(t_01)
			while t[stack_01[-1]] == "1" or s[stack_01[-1]] == "0" or t[stack_01[-1]-1] == "1":
				stack_01.pop()
			t[stack_01[-1]] = "1"
			t_zero -= 1
			stack_01[-1] -= 1
	print(*t, sep="")


st = input().rstrip()
a = []
for item in st:
    a.append(int(item))

a.reverse()
zero_count = 0
for i, item in enumerate(a):
    if item == 0:
        zero_count += 1
    elif zero_count > 0:
        zero_count -= 1
    else:
        a[i] = 0
a.reverse()
print("".join([str(item) for item in a]))

s=[int(x) for x in list(input())]
n=len(s)
b=[0]*n
counter=0
for i in range(n-1,-1,-1):
    if s[i]==0:
        counter+=1
    elif counter>0:
        counter-=1
    else:
        s[i]=0
arr=''
for item in s:
    arr+=str(item)
print(arr)
    


s = input()[::-1]
count= 0 
n = len(s)
s1 = ""
for i in range(n):
	if s[i] == '0':
		count+=1
		s1+='0'
	elif count>0:
		count-=1
		s1+='1'
	else:
		s1 += '0'
s1 = s1[::-1]
print(s1)

S = list(map(int,input().strip()))
N = len(S)

stack = []
for i in range(N):
    s = S[i]
    if s == 0 and stack and stack[-1][0] == 1:
        stack.pop()
    else:
        stack.append((s, i))
T = S[:]
for i in tuple(map(list, list(zip(*stack))))[1]:
    T[i] = 0

print(''.join(map(str, T)))


v,t=0,''
for c in input()[::-1]:
 if c<'1'or v:
  t+=c;v+=1-(c<'1')*2
 else:t+='0'
print(t[::-1])


# -*- coding: utf-8 -*-
# @Date    : 2019-08-21 13:24:15
# @Author  : raj lath (oorja.halt@gmail.com)
# @Link    : link
# @Version : 1.0.0

import sys
sys.setrecursionlimit(10**5+1)

inf     =  int(10 ** 20)
max_val =  inf
min_val = -inf

RW  = lambda : sys.stdin.readline().strip()
RI  = lambda : int(RW())
RMI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
RWI = lambda : [x for x in sys.stdin.readline().strip().split()]

given = input()[::-1]
zeros = 0
lens  = len(given)
rets  = ''
for i in range(lens):
    if given[i] == '0':
        zeros += 1
        rets += '0'
    elif zeros > 0:
        zeros -= 1
        rets += "1"
    else:
        rets += '0'
rets = rets[::-1]
print(rets)





a=input()
a=list(a)
l=[]
for i in range(0,len(a)):
    l.append([a[i],i])
i=1
while(i<len(l)):
    if l[i][0]=='0' and l[i-1][0]=='1':
        l.pop(i)
        l.pop(i-1)
        i-=2
    if i==-1:
        i=0
    i+=1
for i in range(0,len(l)):
    a[l[i][1]]=0
print (*a,sep="")
    

s = input()[::-1]
ans=''
c=0
for i in s:
    if i=='0':
        ans+='0'
        c+=1
    elif c>0:
        ans+='1'
        c-=1
    else:
        ans+='0'
print(ans[::-1])                


st = input().rstrip()
a = []
for item in st:
    a.append(int(item))
 
a.reverse()
zero_count = 0
for i, item in enumerate(a):\
    #huaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
    #where all this peps got this kind of solutionnnnnnnnnn
    #huaawdkaowkdoakwdoj
    #zsevorinpunu8opzersvnopsvzerveorunppioupenirszuinorpsuozserinpvnopugiyuoprgeinwpuirzsdtgnopuvxynpozsdrtuoprtudsz
    if item == 0:
        zero_count += 1
    elif zero_count > 0:
        zero_count -= 1
    else:
        a[i] = 0
    #print(i,item,zero_count)
a.reverse()
print("".join([str(item) for item in a]))


pp = input()
if len(pp) == 1:
    print('0')
    return
z = 1 if pp[0]=='0' else 0
zc = [z]
l = 1
lndl = [l]
for p in pp[1:]:
    l = max(z + 1, l + (1 if p == '1' else 0))
    z += 1 if p == '0' else 0
    lndl.append(l)
    zc.append(z)
lnda = lndl[-1]
o = 1 if pp[-1]=='1' else 0
oc = [o]
l = 1
lndr = [l]
for p in reversed(pp[:-1]):
    l = max(o + 1, l + (1 if p == '0' else 0))
    o += 1 if p == '1' else 0
    lndr.append(l)
    oc.append(o)
oc.reverse()
lndr.reverse()
qq = []
ez = 0
if pp[0] == '1':
    if max(oc[1], lndr[1] + 1) != lnda :
        qq.append('1')
    else:
        qq.append('0')
        ez += 1
else:
    qq.append('0')
for p, l, o, z, r in zip(pp[1:-1],lndl, oc[2:], zc, lndr[2:]):
    if p == '1':
        if max(l + o, z + ez + 1 + r) != lnda:
            qq.append('1')
        else:
            qq.append('0')
            ez += 1
    else:
        qq.append('0')

qq.append('0')
print(''.join(qq))


s = input()

res = ""
min_dif = 0

for i in range(len(s)):
    if s[len(s)-i-1] == "0":
        res = "0"+res
        min_dif = min([-1, min_dif-1])
    else:
        if min_dif >= 0: res = "0"+res
        else: res = "1"+res
        min_dif = min([1, min_dif+1])
print(res)

s=input()
n=len(s)
b=[0]*n
x=1
l=[]
for i in range(n):
    l.append(i)
while(x==1):
    x=0
    for i in range(len(s)-1):
        if(s[i]=='1' and s[i+1]=='0'):
            x=1
            b[int(l[i])]=1
            l[i]=l[i+1]=1000000
    s=s.replace("10","")
    l=list(set(l))
    if(x==1):
        l.remove(1000000)
print(*b,sep="")

def main():
    s = input()
    n = len(s)

    st = []
    flags = [False for i in range(n)]

    for i in range(n):
        if s[i] == '1':
            st.append(i)
        elif len(st) != 0:
            st.pop()
    
    for i in range(len(st)):
        flags[st[i]] = True

    for i in range(n):
        if flags[i] == True:
            print("0", end = '')
        else:
            print(s[i], end = '')
    print()


main()

s = input()[::-1]
count= 0 
n = len(s)
s1 = ""
for i in range(n):
	if s[i] == '0':
		count+=1
		s1+='0'
	elif count>0:
		count-=1
		s1+='1'
	else:
		s1 += '0'
s1 = s1[::-1]
print(s1)

s=input()
ans=list(s)
n=len(s)
dp=[0]*n
i=0
j=1
while j<n:
    if s[i]=="1" and s[j]=="0":
        dp[i]=1
        dp[j]=1
       # print(i,j)
        if i>0:
            while dp[i]==1 and i>0:
                i-=1
        j+=1
    else:
        j+=1
        i=j-1
#print(dp)
for i in range(n):
    if dp[i]==0:
        ans[i]="0"
print("".join(ans))


s = input()
s = list(s)
l = len(s) - 1
z = 0
for i in range(l, -1, -1):
	if s[i] == '0':
		z += 1
	elif z:
		z -= 1
	else:
		s[i] = '0'

s = ''.join(s)
print(s)

s=list(map(int,input()))
stack=[]
for i in range(len(s)):
    if s[i]==1:
        stack.append(i)
    elif len(stack)!=0:
        stack=stack[:-1]
for i in stack:
    s[i]=0
s=list(map(str,s))
print(''.join(s))


s = input()

s = [*s]
c = m = 0

for i in range(len(s) - 1, -1, -1):
	c += -1 if s[i] == '0' else 1
	if c > m:
		s[i] = '0'
		m = c

print(''.join(s))

line = input()
res = []
zer = 0
one = 0

for i in range(len(line)):
    ind = len(line) - 1 - i

    if line[ind] == '0':
        res.append('0')
        zer += 1
    else:
        if zer <= one:
            res.append('0')
            zer += 1
        else:
            res.append('1')
        one += 1

            
for i in range(len(res)):
    print(res[len(res) - 1 - i], end = '')
print('\n', end = '')


s = input()
res = ['0'] * len(s)
stk = []
for i in range(len(s)):
    if s[i] == '0':
        if len(stk) > 0:
            res[stk[-1]] = '1'
            stk.pop()
    else:
        stk.append(i)
print(''.join(res))


data = [int(i) for i in input()]
n = len(data)
minval = [0]* n
minval[-1] = 2 * data[-1] - 1  

for i in range(n-2, -1, -1):
    if data[i] == 1:
        minval[i] = min(1, minval[i+1] + 1)
    else:
        minval[i] = min(-1, minval[i+1] - 1)

ans = [i for i in data]
for i in range(n-1, -1, -1):
    if minval[i] == 1:
        ans[i] = 0
ans2 = [str(i) for i in ans]

print("".join(ans2))
# print(minval)