H. Скромные подстроки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два целых числа $$$l$$$ и $$$r$$$.

Назовём число $$$x$$$ скромным, если $$$l \le x \le r$$$.

Найдите строку длины $$$n$$$, состоящую из цифр, с наибольшим возможным количеством подстрок, являющихся скромными числами. Подстроки, имеющие ведущие нули, не учитываются. Если возможных ответов несколько, найдите лексикографически минимальный.

Если одно и то же число встречается несколько раз как подстрока, то при подсчёте количества скромных подстрок, оно будет тоже учитываться несколько раз.

Входные данные

Первая строка содержит одно целое число $$$l$$$ ($$$1 \le l \le 10^{800}$$$).

Вторая строке содержит одно целое число $$$r$$$ ($$$l \le r \le 10^{800}$$$).

Третья строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\,000$$$).

Выходные данные

В первой строке выведите наибольшее возможное количество скромных подстрок.

Во второй строке выведите строку длины $$$n$$$ имеющую ровно такое число скромных подстрок.

Если существует несколько таких строк, выведите лексикографически минимальную из них.

Примеры
Входные данные
1
10
3
Выходные данные
3
101
Входные данные
1
11
3
Выходные данные
5
111
Входные данные
12345
12346
6
Выходные данные
1
012345
Примечание

В первом примере у строки «101» скромные подстроки «1», «10», «1».

Во втором примере у строки «111» скромные подстроки «1» ($$$3$$$ раза) и «11» ($$$2$$$ раза).