Cellular Automata

A square field is divided into $n \times n$ cells. Each cell holds one of two states, 0 or 1. At regular intervals called generations, every cell updates its state at the same time, based on the states that it and its neighbours held in the previous generation.

An interior cell has four neighbours: the cells above and below it, and the cells to its left and to its right. A corner cell has only two neighbours. The remaining cells along the edge of the field have three neighbours.

One way to update a cell is to look at the sum of the states that it and its neighbours held in the previous generation. That sum lies between 0 and 5, so an update rule fits in 6 bits. The rule 0 0 1 0 0 1, for instance, says that the new state of a cell is

• 0 if the sum was 5,
• 0 if the sum was 4,
• 1 if the sum was 3,
• 0 if the sum was 2,
• 0 if the sum was 1,
• 1 if the sum was 0,

where the sum means the sum of the previous states of the cell and of all its neighbours. Each rule is identified by its binary code: the 6 bits $a\,b\,c\,d\,e\,f$ correspond to the decimal value $a \times 32 + b \times 16 + c \times 8 + d \times 4 + e \times 2 + f$. The rule above has the binary number 001001, so its decimal value is 9.

Take $n = 4$ with the starting state

1111
1111
1111
1111

Rule 9 turns it into

1001
0000
0000
1001

after one generation, and into

0000
0110
0110
0000

after two generations.

Given a size $n$, a number of generations $g$, a starting state $s$ and an ending state $e$, find the rule with the smallest decimal value that turns $s$ into $e$ after exactly $g$ generations.

$n$ is at most 30 and $g$ is at most 50.

The input consists of the following lines.

1. The first line contains two positive integers, the size $n$ and the number of generations $g$.
2. Each of the next $n$ lines contains $n$ digits, each of them 0 or 1. These $n$ lines give the starting state $s$.
3. The next line is empty.
4. Each of the following $n$ lines contains $n$ digits, each of them 0 or 1. These $n$ lines give the ending state $e$.

Print a single integer, the smallest decimal value of a rule that turns $s$ into $e$ after exactly $g$ generations. Print -1 if no rule does this.