AT_past19_o 15パズル

A $ 4\times 4 $ grid is said to be **good** if it is in the following state: > For every integer $ i $ between $ 1 $ and $ 15 $ , inclusive, there is exactly one cell with that integer written on it. > No other cell has something written on it. In other words, there is exactly one cell with nothing written on it. You are given two distinct good grids $ S $ and $ T $ . Here, the good grid $ S $ is given by $ 16 $ integers $ S_{i,j} $ $ (1\leq i,j\leq 4) $ . If $ 1\leq S_{i,j}\leq 15 $ , it means that the cell in the $ i $ -th row from the top and $ j $ -th column from the left has $ S_{i,j} $ written on it; if $ S_{i,j}=-1 $ , it means that the cell in the $ i $ -th row from the top and $ j $ -th column from the left has nothing written on it. Likewise, $ T $ is given by $ 16 $ integers $ T_{i,j} $ $ (1\leq i,j\leq 4) $ . Find the minimum number of times of performing the following operation to make the grid equal to $ T $ , starting from $ S $ . If the grid cannot be made equal to $ T $ with $ 30 $ operations or less (including the case where any number of operations can do so), print $ -1 $ instead. - Choose a cell adjacent to the cell with nothing written on it, and write the integer written on the chosen cell to the empty cell. Then, erase the integer written on the chosen cell.

The input is given from Standard Input in the following format: > $ S_{1,1} $ $ S_{1,2} $ $ S_{1,3} $ $ S_{1,4} $ $ S_{2,1} $ $ S_{2,2} $ $ S_{2,3} $ $ S_{2,4} $ $ S_{3,1} $ $ S_{3,2} $ $ S_{3,3} $ $ S_{3,4} $ $ S_{4,1} $ $ S_{4,2} $ $ S_{4,3} $ $ S_{4,4} $ $ T_{1,1} $ $ T_{1,2} $ $ T_{1,3} $ $ T_{1,4} $ $ T_{2,1} $ $ T_{2,2} $ $ T_{2,3} $ $ T_{2,4} $ $ T_{3,1} $ $ T_{3,2} $ $ T_{3,3} $ $ T_{3,4} $ $ T_{4,1} $ $ T_{4,2} $ $ T_{4,3} $ $ T_{4,4} $

Print the minimum number of times of performing the operation in the problem statement to make the grid equal to $ T $ , starting from $ S $ . If the grid cannot be make equal to $ T $ with $ 30 $ operations or less, print $ -1 $ instead.

### Sample Explanation 1 We denote by $ (i,j) $ the cell in the $ i $ -th row from the top and $ j $ -th column from the left in the grid. In $ S $ , the empty cell is $ (4,4) $ . One can perform three operations to obtain $ T $ . - Choose $ (3,4) $ . Write $ 12 $ to $ (4,4) $ , and erase the integer written on $ (3,4) $ . - Choose $ (3,3) $ . Write $ 11 $ to $ (3,4) $ , and erase the integer written on $ (3,3) $ . - Choose $ (2,3) $ . Write $ 7 $ to $ (3,3) $ , and erase the integer written on $ (2,3) $ . On the other hand, one cannot obtain $ T $ with two operations or less, so print $ 3 $ .  ### Sample Explanation 2 One cannot obtain $ T $ with $ 30 $ operations or less, so print $ -1 $ . ### Constraints - $ -1\leq S_{i,j},T_{i,j}\leq 15 $ - $ S_{i,j},T_{i,j}\neq 0 $ - $ S $ and $ T $ are distinct good grids. - All input values are integers.