셀룰러 오토마타

정사각형 격자를 $n \times n$개의 칸으로 나눈다. 각 칸의 상태는 0 또는 1 중 하나다. 세대라고 부르는 일정한 간격마다 모든 칸이 동시에 상태를 갱신하며, 새 상태는 직전 세대의 자기 자신과 이웃 칸의 상태로 정해진다.

내부 칸의 이웃은 위, 아래, 왼쪽, 오른쪽 네 칸이다. 모서리 칸은 이웃이 두 개뿐이고, 격자 가장자리의 나머지 칸은 이웃이 세 개다.

칸을 갱신하는 한 가지 방법은 직전 세대에서 자기 자신과 이웃의 상태를 모두 더한 값을 보는 것이다. 이 합은 0 이상 5 이하이므로 갱신 규칙은 6비트로 나타낼 수 있다. 예를 들어 규칙 0 0 1 0 0 1은 각 칸의 새 상태를 이렇게 정한다.

• 합이 5이면 0
• 합이 4이면 0
• 합이 3이면 1
• 합이 2이면 0
• 합이 1이면 0
• 합이 0이면 1

여기서 합은 그 칸과 이웃 전부의 이전 상태를 더한 값이다. 규칙은 이진 코드로 구분한다. 6비트 $a\,b\,c\,d\,e\,f$는 십진값 $a \times 32 + b \times 16 + c \times 8 + d \times 4 + e \times 2 + f$에 대응한다. 위 규칙의 이진수는 001001이므로 십진값은 9다.

$n = 4$이고 시작 상태가 다음과 같다고 하자.

1111
1111
1111
1111

규칙 9를 적용하면 한 세대 뒤에는

1001
0000
0000
1001

이 되고, 두 세대 뒤에는

0000
0110
0110
0000

이 된다.

크기 $n$, 세대 수 $g$, 시작 상태 $s$, 끝 상태 $e$가 주어진다. 정확히 $g$세대 뒤에 $s$를 $e$로 바꾸는 규칙 중 십진값이 가장 작은 것을 찾아라.

$n$은 30 이하, $g$는 50 이하다.

입력은 다음 줄로 이루어진다.

1. 첫째 줄에 크기 $n$과 세대 수 $g$를 나타내는 양의 정수 두 개가 주어진다.
2. 다음 $n$개 줄에는 0 또는 1인 숫자가 $n$개씩 주어진다. 이 $n$개 줄이 시작 상태 $s$다.
3. 그다음 줄은 빈 줄이다.
4. 이어지는 $n$개 줄에는 0 또는 1인 숫자가 $n$개씩 주어진다. 이 $n$개 줄이 끝 상태 $e$다.

정확히 $g$세대 뒤에 $s$를 $e$로 바꾸는 규칙의 십진값 중 가장 작은 값을 정수 하나로 출력한다. 그런 규칙이 없으면 -1을 출력한다.