Start

2016-09-08 21:30 CEST

Week 2 Contest

End

2016-09-15 21:30 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -320 days 23:08:19

Time elapsed

168:00:00

Time remaining

0:00:00

Problem C
N-Puzzle

$N$-puzzle is a puzzle that goes by many names and has many variants. In this problem we will use the $15$-puzzle. It consists of a $4$-by-$4$ grid of sliding squares where one square is missing. The squares are labeled with uppercase letters ’A’ through ’O’, with the desired layout as follows:

\includegraphics{table}

It can be useful (for example, when solving the puzzle using a computer) to define the "scatter" of a puzzle as the sum of distances between each square’s current position and its position in the desired layout. The distance between two squares is their Manhattan distance (the absolute value of the sum of differences between the two rows and the two columns).

Write a program that calculates the scatter of the given puzzle.

Input

Four lines of input contain four characters each, representing the state of the puzzle.

Output

Output the scatter of the puzzle on a single line.

Sample Input 1 Sample Output 1
ABCD
EFGH
IJKL
M.NO
2
Sample Input 2 Sample Output 2
.BCD
EAGH
IJFL
MNOK
6