Hide

Problem D
Siffrid's Digit Sum

Submissions to this problem will only be marked as accepted if they receive at least a score of 100
Languages en sv

Siffrid loves playing with numbers! Right now, she is playing with the integer $N$.

She wonders how to create the smallest and largest number that have the same digit sum and number of digits as $N$. Can you help her?

The digit sum of a number is defined as the sum of all its digits.

For example, the digit sum of the number $1234$ is:

\[ 1 + 2 + 3 + 4 = 10, \]

and the digit sum of the number $220$ is:

\[ 2 + 2 + 0 = 4. \]

Input

Input consists of the single integer $N$ ($1 \le N \le 10^9$).

Output

Print two integers on the same line: the smallest and largest number with the same digit sum and number of digits as $N$. The numbers should be separated by a space.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Group

Points

Constraints

$1$

$40$

$N \leq 10^5$

$2$

$60$

No additional constraints.

Explanation of Sample 1

We cannot create a number smaller than $101$ with the same digit sum and number of digits as $N$. Numbers like $11$ and $2$ have the same digit sum as $N$ but do not have the same number of digits as $101$.

Sample Input 1 Sample Output 1
101
101 200
Sample Input 2 Sample Output 2
878
599 995
Sample Input 3 Sample Output 3
1337
1049 9500

Please log in to submit a solution to this problem

Log in