Problem E
Colosseum of Fools
Deep in the caverns of a fallen kingdom, lies a sacred
battleground for warriors all across the lands to test their
skills. Tonight,
The keeper to the gate of the Colosseum wishes to compare
the relative strengths of each of these
One bug is said to be stronger than another if their charm list is lexicographically smaller than the other’s charm list. If two bugs have the same charm list, the one that appears earlier in the keeper’s list is stronger. Given this, can you produce a list of tonight’s competitors, in order of their strength?
Input
The first line of input contains two integers
The next
The next
It is guaranteed that the total length of all charm names is
at most
Output
Output
Notes
For the first sample test case, the charm lists for the three contestants are
-
quickslashspelltwisterdreamwielder
-
quickslashspelltwisterdreamshield
-
shamanstonedreamwielder
It can be seen from this that the order in the sample output is correct.
For the second sample test case, note that a bug may use multiple copies of a charm, and the charm’s names may not be in any known language.
Note that a string
-
is a prefix of , but . -
There exists some
such that for all , and . Here, characters are ordered alphabetically, so a is the smallest, b is the second smallest, etc.
Sample Input 1 | Sample Output 1 |
---|---|
3 5 dreamwielder shamanstone quickslash spelltwister dreamshield 3 3 4 1 3 3 4 5 2 2 1 |
2 1 3 |
Sample Input 2 | Sample Output 2 |
---|---|
3 2 aa aaa 1 1 6 1 2 1 2 1 2 2 2 2 |
1 3 2 |