Problem D
Cracking The Safe

This particular safe has $9$ buttons with digital displays. Each button shows a single digit in the range $0..3$. When you push one of the buttons, the number it displays is incremented by $1$, circling around from $3$ to $0$. However, pushing a button will also increment the other digits in the same row and the same column as the button pushed.

The safe opens when the display shows nine zeros.

For instance, if you pushed the top-left, center, center, and middle-right buttons, in this order, the safe’s display would change like so:

3 1 2     0 2 3     0 3 3     0 0 3     0 0 0
0 1 1  -> 1 1 1  -> 2 2 2  -> 3 3 3  -> 0 0 0
3 2 3     0 2 3     0 3 3     0 0 3     0 0 0

Write a program to determine if the safe can be opened, and if so, how many button pushes it would take!

Input

The input is a single test case, given as $9$ digits $d$, ($0 \le d \le 3$) on $3$ lines, representing the digits that are initially displayed on the safe’s buttons. Your program will be run multiple times on different inputs.

Output

Output the number of times buttons need to be pushed to open the safe! (The same button may need to be pushed more than once, and you do not have to output which buttons must be pushed.) If the safe cannot be opened, output -1.

3 1 2
0 1 1
3 2 3

4

0 0 3
2 2 3
2 2 1

-1