Новый Мытищинский театр «Фэст» украшен гигантской гирляндой, управляемой компьютером, в которой используются тысячи лампочек. Каждый ряд лампочек в гирлянде управляется набором переключателей, которые контролируются с использованием специальной компьютерной программы. К сожалению, электрики установили неверный набор переключателей, а сегодня вечером состоится открытие театра. Ваша задача — написать программу, которая бы заставила переключатели работать корректно. Ряд лампочек в гирлянде состоит из n лампочек и контролируется n переключателями. Лампочки и переключатели занумерованы слева направо от 1 до n. Каждая лампочка может быть либо включена, либо выключена. Каждый тестовый пример в этой задаче будет содержать начальную и желаемую конечную конфигурации лампочек. Исходно предполагалось, что каждый переключатель будет контролировать одну лампочку. Однако ошибка в электронике привела к тому, что каждый переключатель помимо своей лампочки также изменяет состояние двух (или одной, если основная лампочка находится c краю) соседних с ней. Так, самый левый переключатель (i = 1) изменяет состояние двух самых левых лампочек (1 и 2), а самый правый (i = n) — двух самых правых (n - 1 и n). Каждый из оставшихся переключателей (1 ≤ i ≤ n) изменяет состояние трех лампочек с номерами i - 1, i и i + 1. Исключение составляет единственный случай, когда имеется ровно одна лампочка и один переключатель. В этом случае этот переключатель контролирует эту лампочку. Таким образом, если, к примеру, лампочка 1 включена, а лампочка 2 выключена, то при нажатии на переключатель 1 лампочка 1 выключится, а лампочка 2 включится. Определим минимальную стоимость перехода из одной конфигурации к другой как минимальное количество переключателей, которое требуется нажать, чтобы получить из начальной конфигурации конечную.
Можно представить состояние ряда лампочек как двоичное число, где 0 означает, что лампочка выключена, а 1 — что лампочка включена. Так, в частности, двоичное число 01100 представляет собой ряд из пяти лампочек, среди которых вторая и третья включены, а остальные выключены. Можно превратить эту конфигурацию в конфигурацию 10000, нажав последовательно на переключатели 1, 4 и 5, но дешевле сделать это, просто изменив состояние переключателя 2. Напишите программу, которая определит, на какие переключатели следует нажать, чтобы перевести начальную конфигурацию лампочек в конченую за минимальной стоимость. В некоторых случаях подобное может оказаться невозможным. Отметим, что для компактности представления двоичные числа записываются как десятичные, то есть вместо 01100 и 10000 используются числа 12 и 16 соответственно.
Выходные данные
Для каждого тестового примера выведите в выходной файл одну строку. Она должна содержать номер тестового примера и десятичное число, двоичное представление которого кодирует набор переключателей, которые требуется нажать, чтобы из начальной конфигурации получить конечную. В двоичном представлении этого числа самый правый (наименее значимый) бит должен соответствовать переключателю с номером n, 1 означает, что переключатель следует нажать, а 0 — что нет. Если решения не существует, то вместо этого числа следует вывести слово “impossible”. Если имеется более одного решения, выведите то, которое представляется меньшим десятичным числом. Разделяйте вывод для тестовых примеров пустой строкой. Используйте формат, приведенный в примере.
