Equal Digit Counts

Time limit2sMemory limit128 MB

Summary

Given N up to 10^18, find the smallest number at least N where every digit that appears occurs the same number of times.

Level: Hard8 of 10
Topics: Combinatorics, Backtracking, Greedy, Math
Solved: No attempts yet

Problem

Call a positive integer X an equal-digit-count number if every digit that appears in the decimal representation of X appears the same number of times. Digits that do not appear are ignored. For instance, 2013 satisfies this condition because every appearing digit occurs once, while 2008 does not because 0 occurs twice and 2 and 8 occur once.

Given a natural number N, find the smallest equal-digit-count number that is greater than or equal to N.

Input

The first line contains a natural number N. N is at most 10^18.

Output

Print the answer on the first line. The answer is at most 9,223,372,036,854,775,807.

Examples4

Example 1
Input
```
42
```
Expected output
```
42
```
Example 2
Input
```
2008
```
Expected output
```
2013
```
Example 3
Input
```
987654322
```
Expected output
```
987778899
```
Example 4
Input
```
12345678910
```
Expected output
```
22222222222
```