Annettuna on sudokuruudukko, jonka ensimmäinen rivi on täytetty ja kaikki muut rivit ovat tyhjiä. Tehtäväsi on etsiä jokin tapa ratkaista sudoku.

Sudokussa on tehtävänä sijoittaa jokaiseen ruutuun numero väliltä 1 \ldots 9.
Kunkin numeron tulee esiintyä tasan kerran jokaisella pysty- ja vaakarivillä. Lisäksi kun ruudukko jaetaan 9 osaan 3 \times 3 -pikkuneliöiksi, kunkin numeron tulee esiintyä tasan kerran jokaisessa pikkuneliössä.

Syöte

Syötteen ainoa rivi kuvaa sudokuruudukon ensimmäisen rivin. Rivi sisältää tasan kerran jokaisen numeron väliltä 1 \ldots 9.

Tuloste

Ohjelmasi tulee tulostaa sudokuruudukko ratkaistuna. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Esimerkki

Syöte:

137692548

Tuloste:

137692548
648513729
952478613
871349256
295867134
364251897
589136472
423785961
716924385

Pisteytys

Ohjelmasi saa 100 pistettä, jos se ratkaisee kaikki testitapaukset, ja muuten 0 pistettä.