Алиса и Боб играют в следующую игру. Имеется игровое поле в виде последовательности клеток, расположенных друг за другом

Алиса и Боб играют в следующую игру. Имеется игровое поле в виде последовательности клеток, расположенных друг за другом. На поле расположены три фишки, каждая фишка в своей клетке. За один ход каждый игрок должен переместить одну фишку вправо на произвольное ненулевое число клеток. При этом фишка, которой делается ход, не может встать в клетку, где расположена другая фишка или перепрыгнуть через нее. Выигрывает тот игрок, который смог сделать последний ход.

Рассмотрим пример.

Здесь возможны следующие ходы: сместить правую фишку на одну клетку; сместить среднюю фишку на одну клетку; сместить левую фишку на одну, две, три или четыре клетки.

Алиса всегда делает первый ход, а фишки расставляет Боб. Но Боб не хочет побеждать, он хочет, чтобы Алиса нашла выигрышную стратегию. Поэтому он расставляет фишки так, чтобы Алиса могла гарантированно выиграть.

(Например, в приведенной выше позиции Алиса должна сместить самую левую фишку на три клетки.)


Далее игра зависит от хода Боба. Предположим, он сместит правую фишку на одну клетку. Тогда Алиса в свой ход сместит левую фишку на одну клетку.


Теперь Боб может ходить только средней фишкой. Если он сдвинет ее на одну клетку, то Алиса сдвинет левую фишку на одну клетку.

Бобу остается вновь ходить средней фишкой. Он сдвинет ее на одну клетку, Алиса сдвинет левую фишку на одну клетку и победит.

Для всех других ходов Боба у Алисы также всегда найдется ход, ведущий к победе.

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

Формат входных данных
На вход подается строка представляющая игровое поле. Пустая клетка в строке обозначена нулем, клетка с фишкой обозначена единицей. Длина строки не превосходит 1000 символов. В строке ровно три единицы.

Формат выходных данных
Программа должна вывести строку, представляющую игровое поле после хода Алисы, в том же формате, в котором она поступает на вход.

Методика проверки
Программа проверяется на 32 тестах. Прохождение каждого теста оценивается в 1 балл. Тест из условия задачи при проверке не используется.

Sample Input:
0100001010

Sample Output:
0000101010

Time Limit: 3 секунды
Memory Limit: 256 MB

0