Practice Loops and Conditions with the exercise "Hitori solver"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Loops
Conditions
2D array

Statement

Goal

Each puzzle consists of a square grid with numbers appearing in all squares. The object is to shade squares so:

- No number appears in a row or column more than once.
- Shaded squares do not touch each other vertically or horizontally.
- When completed, all un-shaded squares create a single continuous area.
(use * for shaded squares)

Input

Line 1 : The size of the square, n .
n following lines : Content of the grid made of n numbers.

Output

n following lines : Content of the solved grid made of n numbers and * for shaded squares.

Constraints

2 ≤ n ≤ 8

Example

Input

Output

*1*
234
*2*

Solve it

A higher resolution is required to access the IDE