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

1780. Код Грея

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Денис, Ваня и Федя собрались на свою первую командную тренировку. Федя рассказал, что выучил алгоритм генерации кода Грея:
  1. Создадим список из двух элементов: {0, 1}.
  2. Добавим в конец списка все его элементы в обратном порядке: {0, 1, 1, 0}.
  3. К первой половине элементов списка допишем слева 0, ко второй половине элементов списка допишем слева 1: {00, 01, 11, 10}.
  4. Будем повторять шаги 2 и 3 до тех пор, пока длина всех элементов списка не станет равна n.
Число n называется длиной кода Грея. Так, код длины 3 выглядит следующим образом: {000, 001, 011, 010, 110, 111, 101, 100}.
Когда Денис применил алгоритм Феди, у него получилось, что на k-й позиции в списке (если нумеровать позиции с нуля) стоит двоичное число x. Ваня записал на бумажку числа k и x в двоичной системе счисления. Спустя много лет эта бумажка попала к вам в руки. К сожалению, некоторые цифры на ней стёрлись за эти годы. Сможете ли вы по оставшимся цифрам восстановить числа, которые были на ней записаны?

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

В первой строке записано число k в двоичной системе счисления. Стёршиеся цифры обозначены символом «?». Во второй строке в аналогичном формате записано число x. Длины обоих чисел совпадают и не превосходят 105. Числа могут содержать ведущие нули.

Результат

Если по уцелевшим цифрам можно однозначно восстановить числа k и x, выведите их, заменив символы «?» на символы «0» и «1». Если существует несколько способов сделать это, выведите «Ambiguity». Если Денис или Ваня ошиблись, и восстановить числа невозможно, выведите «Impossible».

Примеры

исходные данныерезультат
0?1
0?0
011
010
?00
??0
Ambiguity
100
100
Impossible
Автор задачи: Дмитрий Полетаев
Источник задачи: XV Открытый командный чемпионат УрГУ по программированию