시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 2 1 50.000%

문제

A set of dominoes, that is, one instance of every unordered pair of the numbers from 0 to n, has been arranged irregularly into a rectangle and the pattern has been recorded by writing the number in each square. For instance, in the figure below the original layout, using a 'standard' set (n = 6) of dominoes, is on the left and the puzzle configuration is on the right. Write a program to recreate the original configuration, guaranteed to exist and to be unique.

입력

Input will consist of a series of puzzles. Each puzzle will start with a line containing an integer n (2 ≤ n ≤ 12). Following this will be n rows each containing n+1 characters from the first n+1 letters of the lower case alphabet, separated by single spaces. The set of puzzles will be terminated by a line containing a single zero (0). The above puzzle is represented in this form in the sample input.

출력

Output will consist of a representation of the original grid in the same format as the input, except that a pair of letters constituting a horizontal domino are separated by an equals sign (‘=’), as shown in the sample output below. Leave a blank line between successive grids.

예제 입력 1

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


예제 출력 1

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