Solve a 9x9 Sudoku puzzle

Given a partially filled 9×9 Sudoku board, fill the empty cells so that the completed board is valid.

A valid Sudoku satisfies:

• Each row contains digits 1–9 with no repetition.
• Each column contains digits 1–9 with no repetition.
• Each of the nine 3×3 sub-boxes contains digits 1–9 with no repetition.

Input

• A 9×9 grid of characters where each cell is either '1'..'9' or '.' (empty).

Output

• Modify the board in-place (or return the completed board) so it becomes a valid solved Sudoku.

Assumptions / Constraints

• The input is guaranteed to have at least one solution.
• You may assume the puzzle has a unique solution unless stated otherwise.

Example

Input:

• Row 1: 5 3 . 7 . .
• Row 2: 6 . 1 9 5 . .

Output: a completed valid Sudoku grid.