Crazy Bits

The Olandicans have invented a strange computer. It has only 12-bit registers to store numbers, and the only command it accepts is SWAP. The SWAP function is called with three arguments $i$, $j$, and $d$. A call swap(i, j, d) swaps the $j$th bit of the $i$th register with its neighboring bit in direction $d$ (0: up, 1: right, 2: down, 3: left).

• Right (1) and left (3) refer to a neighboring bit inside the same register (the $(j+1)$th and $(j-1)$th bit, respectively).
• Up (0) and down (2) refer to the same bit position in a neighboring register (the $(i-1)$th and $(i+1)$th register, respectively).

For example, swap(2, 3, 1) swaps the 3rd and the 4th bits of the 2nd register, and swap(6, 4, 2) swaps the 4th bits of the 6th and the 7th registers.

The Olandicans know the initial values of the registers and want to change them into some other values. Find the minimum number of SWAP calls needed to turn every register into its desired value.

The input consists of multiple test cases. The first line of each test case contains $n$ ($1 \le n \le 16$), the number of registers. The next line contains $n$ integers, where the $i$th number is the initial value of the $i$th register. The next line contains $n$ integers, where the $i$th number is the desired value of the $i$th register. Each register value is an integer between $0$ and $4095$ inclusive (it fits in 12 bits). The input is terminated by a line containing a single zero.

For each test case, print on a single line the minimum number of swaps needed. If it is impossible, print Impossible.