Задача B. Binary king ≡

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁵

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

111111111111

000000111111

111011001000

001011001011