Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Diversity

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 256 megabytes
Time limit: 0.5 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 2\,000\,000\,000).

Output

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

Subtasks

  • Subtask 1 (20%): N \le 100\,000
  • Subtask 2 (30%): All digits of N are the same
  • Subtask 3 (50%): No further restrictions apply
  • Sample Input 1

    1311
    

    Sample Output 1

    1312
    
  • Sample Input 2

    333
    

    Sample Output 2

    340
    
  • Sample Input 3

    12345
    

    Sample Output 3

    12345