Problem

Description

Unless you've been living in the lab all day [1], you would have notice the hot new in-class time-waster: Sudoku! [2] Forget the crossword puzzle. Forget the word jumble. It's all about placing numbers in a 9x9 grid so that each row and column and each 3x3 block contains the digits 1 - 9 only once. W00t!

Since, the instructor hates puzzles but loves algorithms, it's your job to write a Sudoku solver. You will be given a series of Sudoku boards and will have to solve them and output the resulting boards. Once you can do this, imagine all the cute girls you can impress in your Cognitive Psychology class! [3]

Input

The input will be a series of 9x9 Sudoku boards where the blank squares are denoted by 0. Sample input:

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

Multiple input boards will be separated by a blank line.

Output

For each Sudoku board, print out the solved puzzle:

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

Separate multiple boards with a blank line.

[1]	Not that unheard of. I missed out on a few quad festivals because by the time I left the cluster the day star had already descended to its nocturnal sanctuary.