Problem B: Sudoku

Problem B: Sudoku

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 44  Solved: 19
[Submit][Status][Web Board]

Description

Sudoku is a game about filling in digits. It originated from Switzerland, and was published in an American magazine in 1970s, named as "Number Place". It became popular in Japan later. In 1984, it was named as "Sudoku", meaning that there is only one digit in each grid. In 2004, Wayne Gould, who has had been the judge of High Court of Hong Kong, China, brought the game to UK, and it became a popular intellectual game there.



In the game, there is a table of \(9\times 9\) grids. The digits in some of the grids was initially known by the player, but others not known. The player needs to fill in a digit from \(1\) to \(9\) into each unknown grid, so that

- In each row, each digit from \(1\) to \(9\) appears exactly once.
- In each column, each digit from \(1\) to \(9\) appears exactly once.
- In each \(3\times 3\) block with bold border lines, each digit from \(1\) to \(9\) appears exactly once.
- All unknown grids are filled in.

Now, given a Sudoku problem, you need to solve it. The input data guaranteed that each problem has exactly one solution.



Input

A single problem in each input.

There are \(9\) lines, each with \(9\) numbers, representing the digit in each grid, where \(0\) represents an unknown grid.



Output

Output \(9\) lines, each with \(9\) numbers, representing the solution.

Notice that there should be no blank spaces at the end of each line.



Sample Input

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

Sample Output

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

HINT

[Submit][Status]