Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Modest Substrings

time limit per test

5 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

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

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.

Examples

Input

1 10 3

Output

3 101

Input

1 11 3

Output

5 111

Input

12345 12346 6

Output

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/29/2021 21:05:13 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|