EOJ Monthly 2018.1

B. 最大的子串

单点时限: 1.0 sec

内存限制: 256 MB

字符串的大,不在于长,而在于

现在给出由数字组成的字符串 $s$,求出字符串的所有的非空连续子串中,最妙的那个子串。

一个字符串的妙是这样定义的:将这个子串所表示的整数(有可能带前导 0),除以 $10^L$(其中 $L$ 为字符串的长度)。比如说 123456789 的子串 456 的妙为 $\frac{456}{10^3}=0.456$。

输入格式

给出一行一个字符串 $s$ ($1 \le |s| \le 20~000$)。

输出格式

输出最妙的那个子串。如果有多个,输出最短的那个。如果最短的最妙的子串也有多个,输出字典序最小的那个。

样例

Input
123456789
Output
9
Input
321
Output
321