Sudoku is a game about filling in digits. It originated from Switzerland, and was published in an American magazine in 1970s, named as "Number Place". It became popular in Japan later. In 1984, it was named as "Sudoku", meaning that there is only one digit in each grid. In 2004, Wayne Gould, who has had been the judge of High Court of Hong Kong, China, brought the game to UK, and it became a popular intellectual game there.
In the game, there is a table of \(9\times 9\) grids. The digits in some of the grids was initially known by the player, but others not known. The player needs to fill in a digit from \(1\) to \(9\) into each unknown grid, so that
- In each row, each digit from \(1\) to \(9\) appears exactly once.
- In each column, each digit from \(1\) to \(9\) appears exactly once.
- In each \(3\times 3\) block with bold border lines, each digit from \(1\) to \(9\) appears exactly once.
- All unknown grids are filled in.
Now, given a Sudoku problem, you need to solve it. The input data guaranteed that each problem has exactly one solution.