write a go solution for Description:
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<=ql<=qr<=qn) the length of the longest non-decreasing subsequence of the substring s_ls_l+1ldotss_r is equal to the length of the longest non-decreasing subsequence of the substring t_lt_l+1ldotst_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<=p_i_2<=ldots<=p_i_k. The length of the subsequence is k.

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

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

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

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_1s_2 is 11 and the longest non-decreasing subsequnce of the substring t_1t_2 is 01;
- For l=1,r=3 the longest non-decreasing subsequnce of the substring s_1s_3 is 11 and the longest non-decreasing subsequnce of the substring t_1t_3 is 00;
- For l=2,r=3 the longest non-decreasing subsequnce of the substring s_2s_3 is 1 and the longest non-decreasing subsequnce of the substring t_2t_3 is 1;

The second example is similar to the first one.. Output only the code with no comments, explanation, or additional text.