Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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 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.


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).


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


    Sample Output 1

  • Sample Input 2


    Sample Output 2

  • Sample Input 3


    Sample Output 3