Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Problem Note:

  • The given board contains only digits 1-9 and the character '.' .
  • Empty cells are shown by the character ' . '
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The board size is always 9x9.

Example

Input: A given sudoku puzzle:

Output: Solution numbers are marked in blue.