You are given a 9x9 Sudoku board with some of the cells filled in. Your task is to solve the given Sudoku board and find a valid solution. If there are multiple valid solutions, you can print any of them.

A Sudoku board is a 9x9 grid divided into nine 3x3 sub-grids. Each cell in the grid can contain a number from 1 to 9. The goal of Sudoku is to fill in the empty cells of the board in such a way that each row, each column, and each 3x3 sub-grid contains all the numbers from 1 to 9 without repetition.

Input

The input consists of 9 lines, each containing 9 space-separated integers representing the state of the Sudoku board. The given numbers range from 1 to 9, and an empty cell is represented by 0.

Output

Print nine lines, each containing nine space-separated integers representing the solution to the given Sudoku board. If there are multiple valid solutions, you can print any of them.