Problem Description

Determine how many integers in the interval \([A, B]\) have the sum of their digits equal to \(S\). Also, find the smallest integer that satisfies this condition.

Input Format

A single line containing three integers \(A\), \(B\), and \(S\).

Output Format

Output consists of two lines:
- The first line is the count of such integers.
- The second line is the smallest integer.

The input guarantees that there is at least one such number.

Sample Input and Output

Sample Input #1

1 9 5

Sample Output #1

1
5

Sample Input #2

1 100 10

Sample Output #2

9
19

Sample Input #3

11111 99999 24

Sample Output #3

5445
11499

Notes

Data Size and Constraints

For \(100\%\) of the data, it is guaranteed that \(1 \le A, B \le 10^{15}\) and \(1 \le S \le 135\).

Notes

This problem is translated from COCI2007-2008 CONTEST #3 T5 CUDAK.

见题面 Input 部分

见题面 Output 部分