CF1204D2 Kirk and a Binary String (hard version)

给你一个二进制字符串 $s$，让你求出一个新的二进制字符串 $t$，使其满足以下条件： 1. 新字符串的 $0$ 的个数尽可能多。 1. 对于每个 $l,r(1 \le l \le r \le n)$，两个字符串的最长不下降子序列等长。

一行，一个二进制字符串 $s$。

一行，满足条件的二进制字符串 $t$。

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.