CF1110H.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.

给你两个整数 $l$ 和 $r$。

我们称一个整数 $x$ 是谦逊的（modest），当且仅当 $l \le x \le r$。

请构造一个长度为 $n$ 的、仅由数字组成的字符串，使得该字符串中表示谦逊整数的子串数量尽可能多。带有前导零的子串不计入统计。如果存在多个满足条件的字符串，请输出字典序最小的一个。

若某个数字在字符串中作为子串多次出现，则在统计谦逊子串总数时，该数字也应被重复计数。

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$).

第一行包含一个整数 $l$（$1 \le l \le 10^{800}$）。

第二行包含一个整数 $r$（$l \le r \le 10^{800}$）。

第三行包含一个整数 $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.

第一行输出最多可能的“谦逊子串”数量。

第二行输出一个长度为 $n$ 的字符串，其恰好包含上述数量的“谦逊子串”。

若存在多个满足条件的字符串，请输出其中字典序最小的一个。

In the first example, string «101» has modest substrings «1», «10», «1».

In the second example, string «111» has modest substrings «1» ($3$ times) and «11» ($2$ times).

在第一个例子中，字符串 «101» 的“谦逊子串”为 «1»、«10» 和 «1»。

在第二个例子中，字符串 «111» 的“谦逊子串”为 «1»（共 $3$ 次）和 «11»（共 $2$ 次）。