题目描述

在一个 \(4\times 4\) 的棋盘上有 \(8\) 个黑棋和 \(8\) 个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。

给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。

输入格式

前四行，每行 \(4\) 个数字（\(1\) 或者 \(0\)），描述了初始棋盘；

接着是一个空行；

第六到第九行，每行 \(4\) 个数字（\(1\) 或者 \(0\)），描述了最终棋盘。

输出格式

输出文件的第一行是一个整数 \(n\)，表示最少的移动步数。

样例数据

样例输入

1111
0000
1110
0010

1010
0101
1010
0101

样例输出

4

限制与提示