Задача B. Binary king

Автор:M. Sporyshev
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:256 Мб

Условие

Юная разработчица компьютерных игр Алиса создала новую игру и разослала её друзьям на бета-тестирование.

Юный геймер Вася хочет произвести впечатление на Алису, пройдя игру полностью.

На последнем уровне Вася столкнулся с главным боссом — Бинарным королём. В начале боя Бинарный король игры генерирует последовательность K из N двоичных цифр. После этого Вася должен предоставить свою бинарную последовательность V такой же длины.

Васина последовательность оценивается следующим образом. Для каждой позиции i, если Vi = 1 и Ki = 0, Вася получает 1 балл; если Vi = 0 и Ki = 1, Вася теряет 2 балла.

Поскольку Вася играет на максимальной сложности, каждый префикс его последовательности должен содержать нулей не меньше, чем единиц.

Чтобы победить, Вася должен набрать наибольшее возможное количество баллов.

Формат входного файла

Входной файл содержит N символов 0 или 1 — последовательность Короля.

Формат выходного файла

Выходной файл должен содержать N символов 0 или 1 — последовательность Васи, набирающую наибольшее количество баллов. Если существует несколько оптимальных решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
111111111111
000000111111
2
111011001000
001011001011

0.058s 0.022s 9