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 ss (a string which consists of zeroes and ones) of length nn and he is asking you to find a binary string tt of the same length which satisfies the following conditions:
For any ll and rr (1≤l≤r≤n1≤l≤r≤n) the length of the longest non-decreasing subsequence of the substring slsl+1…srslsl+1…sr is equal to the length of the longest non-decreasing subsequence of the substring tltl+1…trtltl+1…tr;
The number of zeroes in tt is the maximum possible.
A non-decreasing subsequence of a string pp is a sequence of indices i1,i2,…,iki1,i2,…,ik such that i1<i2<…<iki1<i2<…<ik and pi1≤pi2≤…≤pikpi1≤pi2≤…≤pik. The length of the subsequence is kk.
If there are multiple substrings which satisfy the conditions, output any.
Input
The first line contains a binary string of length not more than 20002000.
Output
Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.
Examples
input
Copy
110
output
Copy
010
input
Copy
010
output
Copy
010
input
Copy
0001111
output
Copy
0000000
input
Copy
0111001100111011101000
output
Copy
0011001100001011101000
Note
In the first example:
For the substrings of the length 11 the length of the longest non-decreasing subsequnce is 11;
For l=1,r=2l=1,r=2 the longest non-decreasing subsequnce of the substring s1s2s1s2 is 1111 and the longest non-decreasing subsequnce of the substring t1t2t1t2 is 0101;
For l=1,r=3l=1,r=3 the longest non-decreasing subsequnce of the substring s1s3s1s3 is 1111 and the longest non-decreasing subsequnce of the substring t1t3t1t3 is 0000;
For l=2,r=3l=2,r=3 the longest non-decreasing subsequnce of the substring s2s3s2s3 is 11 and the longest non-decreasing subsequnce of the substring t2t3t2t3 is 11;
The second example is similar to the first one.
题目大意：
给出一个 串 S ,求一个串 T 要求，等长所有区间的 LIS（最长上升子序列） 相等，0 的个数尽可能多
