Mini sudoku

Problem

A 4 by 4 puzzle must be filled with the digits 1 to 4 so that every row, every column and every 2 by 2 corner box holds each digit once. A 0 marks an empty cell. The given digits never repeat in a row, column or box. Print the completed grid. If there are several answers, print the one found by filling empty cells row by row, trying 1 before 2, 3 and 4. If no answer exists, print NO SOLUTION.

Input, output and limits

Input: Four lines of four digits each, with no spaces.
Output: Four lines with the completed grid, or NO SOLUTION.
Constraints: Each character is a digit from 0 to 4

Examples

Example

Input

Output

A puzzle with exactly one answer.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Find the first empty cell. If there is none, the grid is solved.

Hint 2

Try 1 to 4 in that cell. A digit fits if it is not already in the row, the column or the 2 by 2 box. Reset the cell to 0 when the rest of the grid cannot be solved.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Backtracking problems

Problem

Input, output and limits

Examples

Hints

More Backtracking problems