Problem description

Łamigłówka Sudoku polega na uzupełnieniu planszy 9 × 9 liczbami. W każdej komórce należy wpisać jedną z liczb ze zbioru {1, 2, …, 9}. Liczby umieszczone w każdym wierszu oraz w każdej kolumnie nie mogą się powtarzać. Dodatkowo, planszę dzielimy na dziewięć kwadratów 3 × 3 liniami po trzecim i szóstym wierszu oraz po trzeciej i szóstej kolumnie. W każdym takim kwadracie liczby również nie mogą się powtarzać.

Niektóre z liczb łamigłówki są już wpisane. Napisz program, który rozwiąże łamigłówkę Sudoku.

Wejście

Wejście składa się z dokładnie dziewięciu wierszy. W każdym z nich znajduje się dziewięć znaków. Każdy znak to cyfra od 1 do 9 włącznie lub znak kropki oznaczający, że dane pole planszy nie zostało jeszcze wypełnione.

Wyjście

Wyjście powinno się składać z dziewięciu wierszy jak na wejściu z kropkami zamienionymi na cyfry.

Możesz założyć, że testy są tak dobrane, że zawsze istnieje co najmniej jedno rozwiązanie. Jeżeli istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich.

Przykład

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179