Completing a Magic Square

Interview

Time limit2sMemory limit128 MB

Summary
Given a 3x3 magic square with up to three cells erased (marked 0), fill in the missing positive integers so all rows, columns, and diagonals share the same sum.
Level

Easy3 of 10

Topics
Math, Matrix, Brute force
Solved
No attempts yet

Problem

A 3 by 3 magic square is a square grid in which every row, every column, and both diagonals have the same sum.

Dongju and Sejun accidentally erased up to three cells from a magic square. Erased cells are shown as 0 in the input. Complete the magic square using the remaining numbers.

Every number in the completed magic square is a positive integer not greater than 20,000.

Input

The three rows of the magic square are given from the first line to the third line. Each line contains three integers separated by spaces. An erased cell is given as 0. At most three cells are erased.

Output

Print the completed magic square in the same three-line format as the input.

Examples2

  1. Example 1

    Input
    0 12 12
16 10 0
8 8 14
    Expected output
    6 12 12
16 10 4
8 8 14

  2. Example 2

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