ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1536. Прелести табачного зелья

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Табачное зелье Шира славится своим одурманивающим эффектом. Но вы, должно быть, не знали, что многие хоббиты-родители используют его для воспитания своих отпрысков. Можно накрутить несколько палочек табака и подсунуть ребёнку — пусть играет. А если поскладывать из этих палочек с ним числа, то он и арифметике научится. Давайте попробуем вникнуть в тонкости хоббитского искусства арифметического счёта на табачных палочках. Плюс получается наложением двух палочек друг на друга крестом, а знак равенства — двумя параллельными палочками. На рисунке показано, как из палочек складываются цифры от 0 до 9.
Problem illustration
Маленькие хоббиты половину своего обучения учатся работать с операцией сложения, поэтому мы так и не смогли получить никаких дополнительных сведений о том, как изображаются остальные действия.
Сэм как-то рассказывал, что в детстве он любил забавляться над своим отцом, перекладывая табачные палочки в выложенном выражении так, что равенство переставало быть верным. Сейчас же для своих детей он придумал новую забаву. Он сам составляет на столе некоторое выражение и просит преобразовать его к верному выражению вида X + Y = Z, переложив при этом не более K палочек. Каждое из чисел X, Y и Z должно содержать не более 8 цифр и не должно иметь ведущих нулей (хотя может равняться нулю). При перекладываниях запрещается менять количество знаков и цифр в выражении. Кроме того, запрещается выкидывать палочки или добавлять новые. Помогите Сэму определить, разрешима ли его задача.

Исходные данные

В первой строке записано выражение вида a1 + a2 = b (0 ≤ a1a2b < 108). Во второй строке дано целое число K (0 ≤ K ≤ 100).

Результат

Определите, можно ли из расположенных на столе палочек получить верное выражение не более, чем за K перекладываний. Если можно, то выведите одно из таких выражений. В противном случае выведите «Impossible».

Примеры

исходные данныерезультат
33+88=127
2
33+88=121
3+3=7
1
Impossible
Автор задачи: Сергей Пупырев
Источник задачи: Восьмое открытое личное первенство УрГУ (3 марта 2007)