Ліза Сонечко
Леді Жук Ліза обожнює математику. Вона кілька разів на день рахує свої сім крапочок. Щоб ще більше вдосконалити свої навички, вона навчається в Коледжі Членистоногих на Лузі. Сьогодні вона готується до іспиту у свого професора, Сотніжки Калькулона. На іспиті студент має показати кількість ніг Калькулона на дисплеї калькулятора. Цей калькулятор був знайдений багато років тому серед іншого сміття на звалищі. Деякі з його клавіш не працюють, а дисплей має лише три цифри. Робочі клавіші утворюють підмножину:
0 1 2 3 4 5 6 7 8 9 + − / =
Кнопки "0", "1", ..., "9" називаються цифровими кнопками, "=" є кнопкою дорівнює, а інші кнопки є операторними кнопками. Калькулятор також має клавішу "C" для скидання, але лише Калькулон може її натискати, тому ми не будемо розглядати її в цій задачі. Результат іспиту залежить від кількості натискань клавіш для отримання заданого значення. Ліза хоче отримати ідеальний бал, тому їй потрібно знайти найкоротшу можливу послідовність натискань клавіш.
Робота калькулятора описується діаграмою нижче. Калькулятор має три регістри: disp зберігає відображуване значення, operator є останнім натиснутим оператором або кнопкою дорівнює, а value є збереженим значенням. На початку іспиту калькулятор знаходиться в стані S, а регістри мають значення, встановлені блоком INIT. Натискання кнопки B змінює стан у напрямку стрілки, позначеної B, і виконується код у блоці поруч зі стрілкою. Результат функції eval(val_1, op, val_2) є результатом оператора, застосованого до val_1 і val_2, тобто, наприклад, val_1 + val_2.
Опис може виглядати складним, але калькулятор працює досить стандартним чином. Є лише кілька специфік і деталей, на які слід звернути увагу:
Він відображає лише невід'ємні цілі числа в діапазоні [0, 999]. Отримання значення поза цим діапазоном у будь-який момент під час іспиту викликає помилку і провал на іспиті.
Результат ділення є цілим числом; точний результат завжди округлюється вниз.
Натискання кнопки дорівнює два або більше разів завжди має такий самий ефект, як і натискання її один раз.
Натискання кнопки дорівнює відразу після операторної кнопки призводить до того, що оператор оцінюється з двома рівними операндами.
Послідовність операторних кнопок поводиться так само, як якщо б була натиснута лише остання кнопка з послідовності.
Наприклад, у першому прикладі введення, 2 2 / 3 + і 2 2 / 3 / є серед оптимальних рішень, тоді як 3 + 2 + 2 + також є рішенням, але довшим. У другому прикладі введення, 3 + 2 + 2 + і 2 + = + 3 + є серед оптимальних рішень.
Вхідні дані
Кожен рядок введення описує один тестовий випадок. Рядок починається з непорожнього списку доступних кнопок (з дозволеного набору), за яким слідує один пробіл і число N (0 ≤ N ≤ 999), що позначає кількість ніг Калькулона, тобто число, яке потрібно відобразити.
Вихідні дані
Для кожного тестового випадку виведіть один рядок з довжиною найкоротшої послідовності кнопок, натискання яких призведе до відображення числа N на калькуляторі. Якщо завдання не може бути вирішено, напишіть рядок зі словом "неможливо".