ほぼ Bobo 数 - Problem

正の整数の十進表記が、同じ整数を二つ連結して得られるとき、その整数を bobo 数と呼びます。例えば、$12341234$ と $3232$ は bobo 数ですが、$1234321$ と $1322$ は bobo 数ではありません。

正の整数について、連続する同じ数字をそれぞれ一つにまとめた結果が bobo 数になるとき、その整数をほぼ bobo 数と呼びます。例えば、$1112223112233$ は、連続する同じ数字をすべてまとめると $123123$ になるので、ほぼ bobo 数です。

Bobo は非常に大きな整数 $n$ を持っており、$n$ 未満の最大のほぼ bobo 数を知りたいと考えています。

入力には 0 個以上のテストケースが含まれ、ファイルの終端で終了します。各テストケースは次の形式です。

最初の行には、先頭にゼロのない整数 $n$（$1\le n\le 10^{5\,000\,000}$）が与えられます。

入力中のすべての $n$ の十進表記の長さの合計は $5\,000\,000$ を超えないことが保証されます。

各テストケースについて、$n$ より真に小さい最大のほぼ bobo 数を表す、先頭にゼロのない整数を出力してください。そのような整数が存在しない場合は、代わりに $-1$ を出力してください。

QOJ.ac