e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Задачі

Божевільний біт

Божевільний біт

Арнольд сконструював дивний комп'ютер; у ньому є лише 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 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #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