Digit Sum in an Interval

Time limit1sMemory limit128 MB

Summary

Count integers in [A,B] with a given digit sum and output the smallest such integer, for bounds up to 10^15.

Level: Medium6 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

The digit sum of an integer is the sum of all digits in its decimal representation.

Given integers A, B, and S, count how many integers x in the interval [A, B] have digit sum S. Also find the smallest integer satisfying the condition.

The input is guaranteed to contain at least one such integer.

Input

The first line contains three integers A, B, and S separated by spaces.

1 ≤ A ≤ B < 10^15
1 ≤ S ≤ 135

Output

On the first line, print the number of integers in [A, B] whose digit sum is S.

On the second line, print the smallest integer satisfying the condition.

Examples3

Example 1
Input
```
1 9 5
```
Expected output
```
1
5
```
Example 2
Input
```
1 100 10
```
Expected output
```
9
19
```
Example 3
Input
```
11111 99999 24
```
Expected output
```
5445
11499
```