在国家计算与高级马戏技能中心，学生们被强烈鼓励进行技术演示。

此时此刻，有 $n$ 名新手表演者排成一排，试图进行一场杂耍表演。不幸的是，他们中没有人对自己的手艺有信心，而且表现得很吃力。因此，一旦有机会，他们就会试图减少自己在表演中的任务，以使工作变得更容易。

每当一名杂耍者手中持有的球超过一个时，他们就会向左右两边的邻居各扔出一个球。如果杂耍者在某个方向上没有邻居，他们就会直接把球扔到台下。所有人同时投掷他们的杂耍球。当没有任何杂耍者持有的球超过一个时，表演结束。

参见下图 J.1，了解该过程的说明。

图 J.1：样例输入 1 的说明。一场有 $n = 8$ 名杂耍者的表演。

作为观众的一员，你对这场表演印象不深。然而，你确实想知道在表演结束时，每位杂耍者手中会剩下多少个球。

输入格式

输入包含： * 一行包含一个长度为 $n$ ($1 \le n \le 10^6$) 的字符串 $s$，由字符 '0'、'1' 和 '2' 组成。$s$ 中的第 $i$ 个字符表示第 $i$ 个人最初持有的杂耍球数量。

输出格式

输出一个长度为 $n$ 的字符串 $s$，由字符 '0' 和 '1' 组成，其中第 $i$ 个字符表示表演结束时第 $i$ 个人手中持有的杂耍球数量。

样例

输入 1

12100212

输出 1

10111111

输入 2

000111222000222111222001

输出 2

111111101111111111111111