Diversity 2
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 1s, and the second contains consecutive 3s. 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