High School Programming League Problems Archive

Sudoku is an ancient Japanese puzzle game. If You do not know the rules, you can read them here.

This variant of the puzzle is called diagonal sudoku.

The goal is to fill a 9x9 playing grid with numbers from 1 to 9 so that in every row and in every column, all nine numbers are different. Also, each of the nine 3x3 parts of the sudoku grid must contain all the different numbers 1 to 9, and finally each of the two diagonals must contain all the different numbers from 1 to 9.

Input

You are given the initial state of a diagonal sudoku board, in the form of nine characters in nine rows. There are no empty spaces between characters in the rows. Unknown fields in sudoku are represented with dots ('.') and all others are represented by digits from 1 to 9. 

Output

Print your solution in the same format as in the input. A real sudoku board must have a unique solution but ours can have multiple solutions. You are allowed to print any of them. For every test case at least one solution exists.

Input:
.45...63.
2...1...5
9..8.5..7
..9...3..
.3.....7.
..8...5..
8..5.3..1
5...2...3
.26...95.

Output:
145792638
287316495
963845217
459271386
632458179
718639542
894563721
571924863
326187954

Scoring

By solving this problem you score 10 points.