Вам даны два целых числа \(l\) и \(r\).
Назовём число \(x\) скромным, если \(l \le x \le r\).
Найдите строку длины \(n\), состоящую из цифр, с наибольшим возможным количеством подстрок, являющихся скромными числами. Подстроки, имеющие ведущие нули, не учитываются. Если возможных ответов несколько, найдите лексикографически минимальный.
Если одно и то же число встречается несколько раз как подстрока, то при подсчёте количества скромных подстрок, оно будет тоже учитываться несколько раз.
Выходные данные
В первой строке выведите наибольшее возможное количество скромных подстрок.
Во второй строке выведите строку длины \(n\) имеющую ровно такое число скромных подстрок.
Если существует несколько таких строк, выведите лексикографически минимальную из них.
Примечание
В первом примере у строки «101» скромные подстроки «1», «10», «1».
Во втором примере у строки «111» скромные подстроки «1» (\(3\) раза) и «11» (\(2\) раза).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
10
3
|
3
101
|
|
2
|
1
11
3
|
5
111
|
|
3
|
12345
12346
6
|
1
012345
|