A12453 | Modest Substrings

You are given two integers $l$ and $r$ .

Let's call an integer $x$ modest, if $l \le x \le r$ .

Find a string of length $n$ , consisting of digits, which has the largest possible number of substrings, which make a modest integer. Substring having leading zeros are not counted. If there are many answers, find lexicographically smallest one.

If some number occurs multiple times as a substring, then in the counting of the number of modest substrings it is counted multiple times as well.

The first line contains one integer $l$ ( $1 \le l \le 10^{800}$ ).

The second line contains one integer $r$ ( $l \le r \le 10^{800}$ ).

The third line contains one integer $n$ ( $1 \le n \le 2\,000$ ).

In the first line, print the maximum possible number of modest substrings.

In the second line, print a string of length $n$ having exactly that number of modest substrings.

If there are multiple such strings, print the lexicographically smallest of them.