Decoding Ancient Messages

Time limit2sMemory limit128 MB

Summary

Choose one cell in each row and column so the chosen letters, sorted ascending, are lexicographically smallest.

Level: Medium7 of 10
Topics: Graph, Greedy
Solved: No attempts yet

Problem

Professor Y digs up ancient artifacts. The stone plates he found recently carry $N^2$ letters each, arranged in an $N \times N$ grid, and one plate holds one message of length $N$ . The procedure for reading a plate is this.

Pick $N$ letters from the grid so that no two picked letters lie in the same row and no two lie in the same column.
Concatenate the picked letters in any order you like to form a string of length $N$ .
The message of the plate is the lexicographically smallest string that step 2 can produce.

Letters compare by their ASCII values, so $\mathtt{A} < \mathtt{B} < \cdots < \mathtt{Z} < \mathtt{a} < \mathtt{b} < \cdots < \mathtt{z}$ .

Given one plate, find its message.

Input

The input format is this.

N
c11c12...c1N
c21c22...c2N
:
:
cN1cN2...cNN

The first line contains an integer $N$ ( $1 \le N \le 50$ ). Each of the next $N$ lines contains a string of $N$ characters. Every character is an uppercase or lowercase English letter (A-Z, a-z).

Output

Print the message of the plate on one line.

Examples3

Example 1
Input
```
3
aab
czc
baa
```
Expected output
```
aac
```

Example 2

Input

36
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiQiiiiiiiiiiiiiiiQiiiiiiiii
iiiiiiiiiiQQQiiiiiiiiiiQQQQiiiiiiiii
iiiiiiiiiiQQQQQiiiiiiiQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQiiiiiiiiiii
iiiiiiiiiiiiQQQQQQQQQQQQQiiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiQQQQQQQQQQQQQQQQQiiiiiiiii
iiiiiiQiiiQQQQQQQQQQQQQQQQQiiiQiiiii
iiiiiiQQiQQQQQQQQQQQQQQQQQQiiQQiiiii
iiiiiiiQQQQQQQQQQQQQQQQQQQQiQQiiiiii
iiiiiiiiiQQQQQQQQQQQQQQQQQQQQiiiiiii
iiiiiiiiQQQQQiiQQQQQQQQiiQQQQQiiiiii
iiiiiiQQQQQQiiiiQQQQQiiiiQQQQQQiiiii
iiiiiQQQQQQQQiiiQQQQQiiQQQQQQQQiQiii
iiiQQQQQQQiiQiiiQQQQQiiQiiQQQQQQQQii
iQQQQQQQQQiiiiiQQQQQQQiiiiiiQQQQQQQi
iiQQQQQQQiiiiiiQQQQQQQiiiiiiiiQQQiii
iQQQQiiiiiiiiiQQQQQQQQQiiiiiiiiQQQii
iiiiiiiiiiiiiiQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii
iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

Expected output

QQQQQQQQQQQQQQQQQQQQQQQQQiiiiiiiiiii

Example 3
Input
```
3
Acm
aCm
acM
```
Expected output
```
ACM
```