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 if you solve it. But you can hack the previous 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<=l<=r<=n) 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 10^5.

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.