Задача A. Запертая комната ≡

Условие

Тимофей пытается найти выход из квестовой комнаты и ему осталось пройти последнее испытание - автомат, который блокирует входную дверь. У автомата есть индикатор, на котором светится число 1. Еще у автомата есть три кнопки, первая из которых увеличивает число на индикаторе вдвое, вторая - возводит число на индикаторе в квадрат, третья - стирает у числа последнюю цифру. Индикатор позволяет выводить только k разрядов числа, поэтому если в результате нажатий кнопок получается число большее или равное 10^k, то автомат сбрасывает число на индикаторе снова на 1. То же самое происходит при попытке отбросить последнюю цифру от однозначного числа.

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

Формат входных данных

В единственной строке входного файла через пробел записаны два натуральных числа k и n.

Формат выходных данных

В первой строке выходного файла запишите ответ на задачу. Гарантируется, что организаторы квеста не жульничают и для предложенных k и n ответ существует и не превышает 32. Во второй строке запишите строку, соответствующую последовательности нажатых кнопок. Если существует несколько подходящих строк минимальной длины, вывести нужно лексикографически наименьшую.

Ограничения

2 ≤ n ≤ 100.

2 ≤ k ≤ 6.

Пояснения к примерам

В первом примере Тимофей может превратить 1 в 4 с помощью двух нажатий первой кнопки. Затем превратить 4 в 256 с помощью двух нажатий второй кнопки. Наконец, получить из 256 число 25 с помощью третьей кнопки. Всего потребуется 5 нажатий. Правильной последовательностью также будет строка 12223, но 11223 лексикографически меньше.

Во втором примере Тимофею придется последовательно получать числа 2, 4, 8, 64, 6, 36, 72, 7, 14, 28, 56, 5, 25.

Примеры тестов

6 25

5
11223

2 25

13
1112321311132