Gokigen Naname

Time limit1sMemory limit128 MB

Summary

Fill an n by n grid with one diagonal per cell so each numbered lattice point has exactly that many diagonal endpoints and no diagonal cycle forms.

Level: Medium7 of 10
Topics: Backtracking, DFS, Union-find, Implementation
Solved: No attempts yet

Problem

Gokigen Naname is a grid puzzle from Japan. The board is an $n \times n$ grid of square cells, and some of the $(n+1) \times (n+1)$ lattice points that form the cell corners carry a circled number.

Every cell must contain exactly one diagonal. A diagonal is either a \ joining the cell's top-left corner to its bottom-right corner, or a / joining its top-right corner to its bottom-left corner.

After all diagonals are drawn, for every circled number the count of diagonals whose endpoint lands on that lattice point must exactly equal the number inside the circle. In addition, the diagonals must never join up into a closed loop.

Given a puzzle, write a program that prints a placement satisfying all of these conditions. Only puzzles with a unique answer are given.

Input

The first line contains $n$ , the number of cells along one side of the grid ( $2 \le n \le 7$ ).

The next $n+1$ lines describe the lattice points from top to bottom, one row per line, each line containing exactly $n+1$ characters. A digit gives the required number of diagonals meeting at that point, while . means the point has no number.

Output

Print the solved puzzle as $n$ lines. Line $r$ has $n$ characters, and its $c$ -th character is the / or \ diagonal drawn in the cell at row $r$ , column $c$ . The answer is always unique.

Examples3

Example 1
Input
```
3
1.1.
...0
.3..
..2.
```
Expected output
```
\//
\\\
/\/
```

Example 2

Input

5
.21...
..33.0
......
..33..
0..33.
....11

Expected output

/\\//
//\\\
\\\//
\/\\/
///\\

Example 3
Input
```
2
101
121
020
```
Expected output
```
\/
\/
```