H. Modest Substringstime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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).OutputIn 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.ExamplesInput
1
10
3
Output
3
101
Input
1
11
3
Output
5
111
Input
12345
12346
6
Output
1
012345
NoteIn 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).
1
10
3

3 101 
['dp', 'strings', '*3500']