시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 0 | 0 | 0 | 0.000% |
A positive integer is called a bobo number if its decimal representation can be obtained by concatenating two copies of the same integer. For example, $12341234$ and $3232$ are bobo numbers, while $1234321$ and $1322$ are not.
A positive integer is called an almost bobo number if, after merging all the consecutive equal digits, the resulting number is a bobo number. For example, $\underbrace{111}\underbrace{222}\underbrace{3}\underbrace{11}\underbrace{22}\underbrace{33}$ becomes $123123$ after merging all the consecutive equal digits, and thus is an almost bobo number.
Bobo has a very large number $n$, and he would like to know the largest almomst bobo number less than $n$.
The input contains zero or more test cases, and is terminated by end-of-file. For each test case:
The first line contains an integer $n$ without leading zeros ($1 \leq n \leq 10^{5\,000\,000}$).
It is guaranteed that the total length of the decimal representations of all $n$ in the input does not exceed $5\,000\,000$.
For each test case, output an integer without leading zeros denoting the largest almomst bobo number strictly less than $n$. If there is no such integer, output $-1$ instead.
12345 67890 11111 1000 26782641
12212 67767 11010 -1 26777267