Sudoku

Time limit1sMemory limit128 MB

Summary

Fill every empty cell of a 9x9 Sudoku grid so each row, column, and 3x3 box contains the digits 1 through 9 exactly once.

Level: Medium6 of 10
Topics: Backtracking, Matrix
Solved: No attempts yet

Problem

In Sudoku you are given a large $9 \times 9$ grid divided into nine smaller $3 \times 3$ subgrids. For example:

Given some of the numbers in the grid, your goal is to fill in the remaining cells so that the numbers $1$ through $9$ each appear exactly once in (1) each of the nine $3 \times 3$ subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input

The input contains multiple test cases. Each test case is a single line of 81 characters representing the 81 cells of the grid, given one row at a time from top to bottom. Each character is either a digit ( $1$ through $9$ ) or a period (.) marking an unfilled cell. You may assume that every puzzle has exactly one solution. The end of the input is marked by a single line containing the word end.

Output

For each test case, print the completed grid on a single line: the 81 digits obtained by concatenating the rows from top to bottom, with no periods.

Examples1

Example 1

Input

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end

Expected output

527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936