Məsələlər
Сумасшедший бит
Сумасшедший бит
Арнольд изобрел странный компьютер; в нем имеются только \textbf{12}-битовые регистры для хранения чисел. А единственной командой, которую распознает этот компьютер, является \textbf{swap}. Функция \textbf{swap} вызывается с тремя параметрами \textbf{i}, \textbf{j} и \textbf{d}. Вызов \textbf{swap(i, j, d) }переставляет местами \textbf{j}-й бит \textbf{i}-го регистра с соседним битом в направлении \textbf{d} (\textbf{0}: вверх, \textbf{1}: вправо, \textbf{2}: вниз, \textbf{3}: влево). Считаем, что регистры расположены один под одним, то есть под \textbf{j}-ым битом \textbf{i}-го регистра находится \textbf{j}-й бит \textbf{(i+1)}-го^\{ \}регистра. Биты регистров образуют прямоугольную матрицу, ширина которой равна \textbf{12}, а высота равна количеству регистров. Например, \textbf{swap (2, 3, 1)} переставляет \textbf{3}-й и \textbf{4}-й биты \textbf{2}-го регистра, а \textbf{swap(6, 4, 2)} переставляет \textbf{4}-й бит \textbf{6}-го и \textbf{7}-го регистров. Арнольд знает начальные значения регистров и хочет заменить их на другие значения. Вам следует помочь Арнольду, сделав при этом наименьшее количество вызовов \textbf{swap}.
\InputFile
Входные данные состоят из нескольких тестов. Первая строка каждого теста содержит число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{16}), количество регистров. Следующая строка содержит \textbf{n} целых чисел, где \textbf{i}-е число начальное значение \textbf{i}-го регистра. Следующая строка содержит \textbf{n} целых чисел, где \textbf{i}-е число содержит желаемое значение \textbf{i}-го регистра. Ввод завершается строкой, содержащей ноль.
\OutputFile
Для каждого теста вы должны вывести одну строку, содержащую минимальное количество необходимых обменов. Если это невозможно, выведите "\textbf{Impossible}".
Giriş verilənləri #1
2 2 3 6 2 3 1 1 1 2 3 4 4 5 2 6 0 3 2 2 4 0
Çıxış verilənləri #1
3 Impossible 2