#P1110H. Modest Substrings
-
ID: 4608
Type: RemoteJudge
5000ms
1024MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Modest Substrings
No submission language available for this problem.
Description
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.
Input
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$).
Output
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.
Samples
1
10
3
3
101
1
11
3
5
111
12345
12346
6
1
012345
Note
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).