Diversity 2

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.