题目描述

一个经(jian)典(dan)的问题——鸭瑟夫问题

在食堂阿姨占领鸭山后，$n$个鸭躲到一个洞中

$n$个鸭决定宁愿死也不要成为烤鸭，于是决定了一个自杀方式

$n$个人排成一个圆圈，由第1个鸭开始，每只鸭杀掉相邻的鸭（死的鸭跳过）

这个过程沿着圆圈一直进行，直到最终只剩下一个鸭留下，这个鸭就可以继续活着。

然而其中一只鸭——DengDuck并不想遵从。

问题是，DengDuck一开始要站在什么地方才能避免被处决？

输入格式

输入一个二进制数，表示$n$

没有前导零

输出格式

一个二进制数

表示DengDuck一开始要站在什么地方才能避免被处决

1

1

11

11

1100

1001

提示

对于 $20 \%$的数据，二进制数$n$的长度不超过$10$

对于 $40 \%$的数据，二进制数$n$的长度不超过$60$

对于 $100 \%$的数据，二进制数$n$的长度不超过$10^7$，非常良心

样例一解释

$n=(1)_{10}$

只有DengDuck，DengDuck直接存活

样例二解释

$n=(3)_{10}$

1号杀2号，2号死了，3号杀1号

3号活到最后，所以DengDuck应该站在3号位置

$(3)_{10}=(11)_{2}$

样例三解释

$n=(12)_{10}$

1号杀2号，3号杀4号，5号杀6号，7号杀8号，9号杀10号，11号杀12号

1号杀3号，5号杀7号，9号杀11号，

1号杀5号，9号杀1号

9号活到最后，所以DengDuck应该站在9号位置

$(9)_{10}=(1001)_{2}$