Problem Description

Find how many integers in the interval $[A,B]$ have a digit sum equal to $S$. Also, find the smallest such integer.

Input Format

Input one line with three integers $A,B,S$.

Output Format

Output two lines. The first line is the count of such integers, and the second line is the smallest such integer.

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

1 9 5

1
5

1 100 10

9
19

11111 99999 24

5445
11499

Hint

Constraints

For $100\%$ of the testdata, $1\le A,B\le 10^{15}$, $1\le S\le 135$.

Notes

Translated from COCI2007-2008 CONTEST #3 T5 CUDAK.

Translated by ChatGPT 5