Practice Backtracking with the exercise "Sudoku Solver"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Backtracking

Statement

Goal

Your program must output a solution to a 9x9 sudoku. A sudoku is a Latin Square which has the numbers 1-9 in each row, column, and 3x3 square.

Input

First 9 lines: A string line with 9 digits corresponding to that line. A 0 is used for an empty space.

Output

First 9 lines: A string line with 9 digits corresponding to that line. The original numbers should not have changed, and there should be no zeros left.

Constraints

Example

Input

Output

Solve it

A higher resolution is required to access the IDE