如果一个正整数的十进制表示可以通过将同一个整数拼接两次得到，则称其为 bobo number。例如，12341234 和 3232 是 bobo number，而 1234321 和 1322 则不是。

如果一个正整数在合并所有连续相同的数字后，得到的数字是一个 bobo number，则称其为 almost bobo number。例如，1112223112233 在合并所有连续相同的数字后变为 123123，因此它是一个 almost bobo number。

Bobo 有一个非常大的整数 $n$，他想知道小于 $n$ 的最大的 almost bobo number。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例： 第一行包含一个不含前导零的整数 $n$ ($1 \le n \le 10^{5\,000\,000}$)。

保证输入中所有 $n$ 的十进制表示长度之和不超过 $5\,000\,000$。

输出格式

对于每个测试用例，输出一个不含前导零的整数，表示严格小于 $n$ 的最大的 almost bobo number。如果不存在这样的整数，则输出 $-1$。

样例

输入 1

12345
67890
11111
1000
26782641

输出 1

12212
67767
11010
-1
26777267