Training Site

# Diversity 2

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 2.4 seconds

Alice is interested in diverse numbers. She defines a diverse number as an integer that contains no consecutive repeated digits. For example, the numbers $1311$ and $333$, are not diverse, as the first contains consecutive $1$s, and the second contains consecutive $3$s. Examples of diverse numbers include $1312$, $340$ and $12345$.

Given an integer $N$, help Alice find the smallest diverse number that is not less than $N$.

## Input

There will be a single line containing the integer $N$ ($1 \le N \le 10^{1,000,000}$). Note how large $N$ can be (up to one million digits).

## Output

You should print a single integer – the smallest diverse number that is not less than $N$.

This problem is identical to the original Diversity problem except that $N$ can be much larger and there are no partial marks.

• ### Sample Input 1

1311


### Sample Output 1

1312

• ### Sample Input 2

12345


### Sample Output 2

12345

• ### Sample Input 3

333


### Sample Output 3

340