eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сумасшедший бит

Сумасшедший бит

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Арнольд изобрел странный компьютер; в нем имеются только 12-битовые регистры для хранения чисел. А единственной командой, которую распознает этот компьютер, является swap. Функция swap вызывается с тремя параметрами i, j и d. Вызов swap(i, j, d) переставляет местами j-й бит i-го регистра с соседним битом в направлении d (0: вверх, 1: вправо, 2: вниз, 3: влево). Считаем, что регистры расположены один под одним, то есть под j-ым битом i-го регистра находится j-й бит (i+1)-го^{ }регистра. Биты регистров образуют прямоугольную матрицу, ширина которой равна 12, а высота равна количеству регистров. Например, swap (2, 3, 1) переставляет 3-й и 4-й биты 2-го регистра, а swap(6, 4, 2) переставляет 4-й бит 6-го и 7-го регистров. Арнольд знает начальные значения регистров и хочет заменить их на другие значения. Вам следует помочь Арнольду, сделав при этом наименьшее количество вызовов swap.

Входные данные

Входные данные состоят из нескольких тестов. Первая строка каждого теста содержит число n (1n16), количество регистров. Следующая строка содержит n целых чисел, где i-е число начальное значение i-го регистра. Следующая строка содержит n целых чисел, где i-е число содержит желаемое значение i-го регистра. Ввод завершается строкой, содержащей ноль.

Выходные данные

Для каждого теста вы должны вывести одну строку, содержащую минимальное количество необходимых обменов. Если это невозможно, выведите "Impossible".

Пример

Входные данные #1
2
2 3
6 2
3
1 1 1
2 3 4
4
5 2 6 0
3 2 2 4
0
Выходные данные #1
3
Impossible
2