Hide
Problem C
Cudak
Božo is a strange little boy. Every day he tires his friends with strange questions. Today’s question is: how many integers in the interval $[A, B]$ are there such that the sum of their digits is $S$, and which is the smallest such number?
Write a program that answers Božo’s question so that he can get some sleep.
Input
The input contains three integers $A$, $B$ and $S$ ($1 \le A \le B < 10^{15}$, $1 \le S \le 135$).
Output
The first line should contain the number of integers in the interval with the digit sum equal to $S$.
The second line should contain the smallest such integer.
The input data will guarantee that the first number is at least $1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 9 5 |
1 5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 100 10 |
9 19 |
| Sample Input 3 | Sample Output 3 |
|---|---|
11111 99999 24 |
5445 11499 |