题目描述

天才程序员菜哭武和张老师在玩一个很无聊的游戏。菜哭武有一个由 $0$ 和 $1$ 组成的字符串，张老师给菜哭武一个正整数的二进制表示形式，让菜哭武找到一个相同的子序列。这个游戏太无聊了，张老师想知道菜哭武的 $01$ 串的子序列能构成前多少个整数的二进制形式。

张老师希望你能解决的问题是，已知菜哭武的一个 $01$ 字符串，找到最大的一个正整数 $N$，这个 $01$ 串的所有子序列可以构成所有 $1$ 到 $N$ 的正整数。

子序列是原字符串当中有序但不一定连续的字符组成的字符串。如 $01$ 串 $101$ 有 $1$、$0$、$10$、$11$、$01$、$101$ 一共六个不同的子序列，其中子序列 $1$ 有两种取法。

输入格式

输入一行包含一个字符串 $s$（$1 \leq |s| \leq 10^6$，$|s|$ 为 $s$ 的长度），$s$ 是一个 $01$ 字符串。

输出格式

输出一行，包含一个 $01$ 字符串 $t$，表示 $s$ 能构成的 $1$ 到 $N$ 的最大整数 $N$，使用二进制表示。如果不能构成任意正整数，输出 $0$。

样例输入 #1

101

样例输出 #1

11

样例输入 #2

011

样例输出 #2

1

提示

样例 $1$ 解释：$101$ 可以构成 $1$（取第一个或第三个字符）、$10$（取前两个字符）、$11$（取第一个和第三个字符），但是不能构成 $100$。

样例 $2$ 解释：$011$ 可以构成 $1$（取第二个或第三个字符），不能构成 $10$。