16x16 Sudoku

Time limit3sMemory limit128 MB

Summary

Solve a given 16x16 Sudoku puzzle so each row, column, and 4x4 box contains letters A to P exactly once, given a unique solution exists.

Level: Medium6 of 10
Topics: Backtracking, Matrix, Implementation
Solved: No attempts yet

Problem

You are given a $16 \times 16$ Sudoku board. Fill the board so that every row, every column, and each of the sixteen $4 \times 4$ sub-grids contains each of the uppercase letters from A to P exactly once, with no repeats.

Given the initial state of such a puzzle, output the completed board. Every input is guaranteed to have exactly one solution.

In the original illustration, the left picture shows the initial state of the Sudoku and the right picture shows the solved state.

Input

The initial state of the puzzle is given as $16$ lines, each containing $16$ characters. Each character is either an uppercase letter from A to P (a filled cell) or - (an empty cell).

Output

Print the solved puzzle as $16$ lines of $16$ characters each.

Examples1

Example 1

Input

--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-

Expected output

FPAHMJECNLBDKOGI
OJMIANBDPKCGFLHE
LNDKGFOIJEAHMBPC
BGCELKHPOFIMAJDN
MFHBELPOACKJGNID
CILNKDGAHBMOPEFJ
DOGPIHJMFNLECAKB
JEKAFCNBGIDPLHOM
EBOFPMIJDGHLNKCA
NCJDHBAEKMOFIGLP
HMPLCGKFIAENBDJO
AKIGNODLBPJCEFMH
KDEMJIFNCHGAOPBL
GLBCDPMHEONKJIAF
PHNOBALKMJFIDCEG
IAFJOECGLDPBHMNK