Crazy Bits#2734
Arnold invented a strange computer that only has -bit registers for storing numbers. The only command this computer supports is the swap operation. The swap function is called with three parameters: , , and . A call to swap(i, j, d) swaps the -th bit of the -th register with its neighboring bit in the direction (: up, : right, : down, : left). The registers are arranged one below the other, meaning the -th bit of the -th register has the -th bit of the (i+1)-th register directly below it. The bits of all registers form a rectangular matrix with width and height equal to the number of registers. For example, swap(2, 3, 1) swaps the rd and th bits of the nd register, while swap(6, 4, 2) swaps the th bits of the th and th registers. Arnold knows the initial values of the registers and wants to change them to some desired values. Your task is to help Arnold make the changes with the minimum number of swap calls.
The input consists of multiple test cases. The first line of each test case contains (1 \le n \le 16), the number of registers. The next line contains integers; the -th number is the initial value of the -th register. The following line contains integers; the -th number is the desired value of the -th register. The input is terminated by a line containing zero.
For each test case, output a single line containing the minimum number of swaps needed. If it is not possible, output Impossible.
Example 1