Training Site

# 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 $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 2\,000\,000\,000$).

## Output

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

• 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