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 \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 $10^5$.


-----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:
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 = list(map(int, input()))
ps = [0]
for i in s:
    if i == 0:
        ps.append(ps[-1] + 1)
    else:
        ps.append(ps[-1] - 1)
b = 0
maba = 0
sufmax = [-10 ** 9]
for i in range(len(ps) - 1, 0, -1):
    sufmax.append(max(sufmax[-1], ps[i]))
sufmax = sufmax[::-1]
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 = sufmax[i] - ps[i]
        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))


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[:]
if stack:
    for i in tuple(map(list, zip(*stack)))[1]:
        T[i] = 0

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

s = str(input().strip())
t = list(s[::-1])
cnt = 0
for i,v in enumerate(t):
    if v == '0':
       cnt += 1
    else:
        if cnt:
            cnt -= 1
        else:
            t[i] = '0'
print("".join(t[::-1]))

s = str(input())
n = len(s)
ns = ['0' for i in range(n)]
st = []
for i in range (n):
    if (s[i] == '0'):
        if (len(st)):
            ns[st.pop()] = '1'
    else:
        st.append(i)
print(''.join(ns))

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)

v, ans = 0, ''
for c in input()[::-1]:
    if c == '0' or v:
        ans += c
        v += (1 if c == '1' else -1)
    else:
        ans += '0'
print(ans[::-1])


import sys
import math

def main():
    s = input()
    q = []
    for i in range(len(s)):
        if s[i] == '1':
            q.append(i)
        elif len(q) > 0:
            q.pop();

    result = []
    q = set(q)
    for i in range(len(s)):
        if i in q:
            result.append('0')
        else:
            result.append(s[i])

    print(''.join(result))

    

def __starting_point():
    main()

__starting_point()

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])                


s=input()
ans=['0' for i in range(len(s))]
st=[]
for i in range(len(s)):
    if s[i]=='0':
        if len(st):
            ans[st.pop()]='1'
    else:
        st.append(i)
print(''.join(ans))

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 = ["0"]*len(s)
min_dif = 0
length = len(s)

for i in range(length):
    if s[length-i-1] == "0":
        min_dif = min([-1, min_dif-1])
    else:
        if min_dif < 0: res[length-i-1] = "1"
        min_dif = min([1, min_dif+1])
print("".join(res))

s=input()
n=len(s)
b=[0]*n
l=[]
m=[]
j=0
for i in s:
    if(len(l)==0):
        l.append(i)
        m.append(j)
    elif(l[-1]=='1' and i=='0'):
        l.pop()
        b[m.pop()]=1
    else:
        l.append(i)
        m.append(j)
    j+=1
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()

inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      list(map(int, input().split()))
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

s = input().strip()
n = len(s)
ones = []
stk = []
for i in range(n):
    if len(stk)>0 and stk[-1][0]=='1' and s[i]=='0':
        ones.append(stk[-1][1])
        stk.pop()
    else:
        stk.append((s[i],i))
    #ddprint("i {} stk {}".format(i,stk))
ones.sort()
#ddprint(ones)
ans = ""
cur = 0
for i in ones:
    for j in range(cur, i):
        ans += "0"
    ans += "1"
    cur = i+1
for j in range(cur,n):
    ans += "0"
print(ans)


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])

s = input()
t = list(s)
stack =[]
for i in range(len(s)):
    if t[i]=='1':
        stack.append(i)
    elif len(stack):
        stack.pop()

for i in range(len(stack)):
    t[stack[i]] = '0'
print(''.join(t))

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.pop()
for i in stack:
    s[i]=0
s=list(map(str,s))
print(''.join(s))