#icpc2014springc. [icpc2014spring_c]Decoding Ancient Messages
[icpc2014spring_c]Decoding Ancient Messages
MathJax.Hub.Config({ tex2jax: { inlineMath: [[""], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }
Problem Statement
Professor Y's work is to dig up ancient artifacts. Recently, he found a lot of strange stone plates, each of which has characters arranged in an matrix. Further research revealed that each plate represents a message of length . Also, the procedure to decode the message from a plate was turned out to be the following:
-
Select characters from the plate one by one so that any two characters are neither in the same row nor in the same column.
-
Create a string by concatenating the selected characters.
-
Among all possible strings obtained by the above steps, find the lexicographically smallest one. It is the message represented by this plate.
NOTE: The order of the characters is defined as the same as the order of their ASCII values (that is, ).
After struggling with the plates, Professor Y gave up decoding messages by hand. You, a great programmer and Y's old friend, was asked for a help. Your task is to write a program to decode the messages hidden in the plates.
Input
The input is formated as follows:
:
:
The first line contains an integer (). Each of the subsequent lines contains a string of characters. Each character in the string is an uppercase or lowercase English letter (A
-Z
, a
-z
).
Output
Print the message represented by the plate in a line.