Start

2020-03-30 05:15 AKDT

Kattis Set 11

End

2020-04-06 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -242 days 13:42:40

Time elapsed

164:15:00

Time remaining

0:00:00

Problem F
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