D2. Кёрк и бинарная строка (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между легкой и сложной версиями — длины строк. Вы можете взламывать эту задачу тогда, когда решите ее. Но предыдущую только тогда, когда решите обе задачи.

У Кёрка есть бинарная строка $$$s$$$ (строка, содержащая только нули и единицы) длины $$$n$$$, и он просит вас найти бинарную строку $$$t$$$ такой же длины, для которой выполняются следующие условия:

  • Для любых $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) длина наибольшей неубывающей подпоследовательности в подстроке $$$s_{l}s_{l+1} \ldots s_{r}$$$ равна длине наибольшей неубывающей подпоследовательности в подстроке $$$t_{l}t_{l+1} \ldots t_{r}$$$;
  • Количество нулей в строке $$$t$$$ — максимально возможное.

Неубывающая подпоследовательность в строке $$$p$$$ — это такая последовательность индексов $$$i_1, i_2, \ldots, i_k$$$, что $$$i_1 < i_2 < \ldots < i_k$$$ и $$$p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$$$. Число $$$k$$$ называется длиной подпоследовательности.

Если существует несколько строк, удовлетворяющих условиям, то выведите любую.

Входные данные

Единственная строка содержит бинарную строку длины не больше $$$10^5$$$.

Выходные данные

Выведите бинарную строку, для которой выполняются указанные условия. Если существует несколько таких строк, выведите любую.

Примеры
Входные данные
110
Выходные данные
010
Входные данные
010
Выходные данные
010
Входные данные
0001111
Выходные данные
0000000
Входные данные
0111001100111011101000
Выходные данные
0011001100001011101000
Примечание

В первом примере:

  • Для подстрок длины $$$1$$$ длина наибольшей неубывающей подпоследовательности равна $$$1$$$;
  • Для $$$l = 1, r = 2$$$ наибольшая неубывающая подпоследовательность для подстроки $$$s_{1}s_{2}$$$ — $$$11$$$, для подстроки $$$t_{1}t_{2}$$$ — $$$01$$$;
  • Для $$$l = 2, r = 3$$$ наибольшая неубывающая подпоследовательность для подстроки $$$s_{2}s_{3}$$$ — $$$1$$$, для подстроки $$$t_{2}t_{3}$$$ — $$$1$$$;
  • Для $$$l = 1, r = 3$$$ наибольшая неубывающая подпоследовательность для подстроки $$$s_{1}s_{3}$$$ — $$$11$$$, для подстроки $$$t_{1}t_{3}$$$ — $$$00$$$;

Второй пример аналогичен первому.