Dominosa

Time limit1sMemory limit128 MB

Summary

Reconstruct the domino tiling of an n by n+1 grid where each unordered symbol pair appears exactly once.

Level: Medium7 of 10
Topics: Backtracking, Brute force
Solved: No attempts yet

Problem

With $n$ different symbols there are $n(n+1)/2$ unordered pairs of symbols, counting a pair of two equal symbols as one of them. One domino per pair makes a full set, and a full set covers exactly $n(n+1)$ squares, so it fits an $n$ by $n+1$ rectangle with no gaps and no overlaps.

Lay a full set out that way, erase the edges of the dominoes, and keep only the symbol written in each square. What is left is a puzzle. On the left of the picture below is an original layout of the 28 dominoes made from the seven numbers 0 to 6, and on the right is the same layout with the edges erased.

Read the puzzle and recover the original layout. The layout always exists and it is unique.

Input

The input holds several puzzles.

The first line of a puzzle has an integer $n$ ( $2 \le n \le 12$ ). The next $n$ lines each hold $n+1$ characters separated by single spaces. The characters come from the first $n$ lowercase letters, a through the $n$ th letter of the alphabet.

The $n \times (n+1)$ grid was built by placing each of the $n(n+1)/2$ unordered pairs exactly once, and only one placement matches the grid.

A line holding a single 0 ends the input.

Output

For each puzzle print the recovered layout in the same format as the input, except that the two characters of a horizontal domino are joined by an equals sign (=) instead of a space. Every other gap stays a single space.

Print one blank line between consecutive grids, and no blank line after the last grid.

Examples2

Example 1

Input

7
e d g g f d c c
b g e a a a c f
b b a a a g d g
c e d b c f d g
a f d e e c b b
d c g a b e f f
g d f b f e e c
0

Expected output

e=d g=g f d c=c
b g=e a a a c f
b b=a a a=g d g
c e d b=c f d g
a f d e e c b b
d c=g a b e f=f
g d=f b=f e e=c

Example 2

Input

2
a a b
b b a
3
c b b c
a c b a
a c a b
0

Expected output

a=a b
b=b a

c=b b c
a c b a
a c a=b