Magic Square

Interview

Time limit1sMemory limit128 MB

Summary

Given a 3x3 magic square with up to three erased entries (marked 0), reconstruct the missing values so rows, columns, and diagonals share the same sum.

Level: Medium4 of 10
Topics: Matrix, Math, Brute force
Solved: No attempts yet

Problem

A magic square is made of 3 x 3 small squares. Each small square contains a positive integer no greater than 20,000.

In a magic square, the sums of the numbers in every row, every column, and both diagonals are all equal.

Sanggeun made a magic square, but Changyeong erased some of its numbers. Since Changyeong was kind enough, he erased at most three numbers.

Given a magic square with some numbers erased, write a program that fills in the erased numbers.

Input

Three lines are given. Each line contains three numbers from the magic square. An erased number is given as 0.

Output

Print the magic square after filling in the erased numbers.

Examples3

Example 1
Input
```
4 9 2
3 0 7
8 1 6
```
Expected output
```
4 9 2
3 5 7
8 1 6
```

Example 2

Input

0 12 12
16 10 0
8 8 14

Expected output

6 12 12
16 10 4
8 8 14

Example 3

Input

495 468 0
0 522 414
441 0 549

Expected output

495 468 603
630 522 414
441 576 549