URI Online Judge | 2942

Bits Mixing

By Francisco Elio Parente Arcos Filho, UEA BR Brazil

Timelimit: 1

Bit mixing is an operation performed on a position of an array of integers. When applied to position \(i\) of an array \(A\), it mixes the bits of the number in position \(i\) with those of the adjacent positions of the array. In more exact terms:

\(A[i] \leftarrow A[i-1] \bigoplus A[i] \bigoplus A[i+1]\)

(read: \(A[i]\) receive the xor of \(A[i-1]\) with \(A[i]\) with \(A[i+1]\))


The operator \(\bigoplus\) symbolizes the-xor bitwise operation.

By definition, the operation can only be applied on positions having both adjacent positions.

Your task is, given two configurations of an array, to calculate the minimum number of bits mixing to transform the first array into the second.


The first line of the input consists of an integer N (1 ≤ N ≤ 105) representing the size of the array. The second line of the input has N integers Ai (0 ≤ Ai < 231) representing the initial array configuration. The third line of the input has N integers Bi (0 ≤ Bi < 231) representing the final configuration of the array.


The output consists of a single line containing the minimum number of operations to transform array A into array B or the message "IMPOSSIBLE" if it is not possible to do so.

Input Samples Output Samples


3 5 8

3 14 8



1 2 4 8 16

1 7 31 28 16



1 2 3 4 5 6

1 5 4 3 2 6