1007 DNA Sorting

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

DNAの整列

問題

文字列の「非整列度」の定め方の1つとして、列中で大きい方が手前に来るような2つの要素の組の個数を用いる方法がある。例えば、文字列「DAABEC」は、Dはその右側にあるうちの4文字より大きく、Eはその右側にある文字Cよりも大きいので、非整列度は5となる。この定め方は、「列中の反転の個数」と呼ばれる。「AACEDGG」はただ1つの反転(EとD)を持つ、つまりほとんど整列されている。いっぽう、「ZWQM」は6つの反転を持つ。これはちょうど整列された列の反転であり、もっとも整列されていない。

あなたは複数のDNA文字列を整理する必要がある(DNA文字列はA,C,G,Tの4文字のみからなる)。しかし、あなたは辞書順ではなく、「整列度」に基いて「最も整列されたもの」から「最も整列されていないもの」の順番に文字列を並べたいと考えている。なお、与えられるDNA文字列の長さは全て同じである。

入力

先頭行には2つの整数がある。1つは文字列の長さを与える正整数n(0<n≦50)、もう1つは文字列の個数を与える正整数m(0<m≦100)である。続くm行には、それぞれn文字のDNA文字列が書かれている。

出力

与えられたDNA文字列を、「最も整列されたもの」から「最も整列されていないもの」の順番で出力しなさい。2つの文字列が同じように整列されている場合は、元の順番にならって出力すること。

入力例

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

出力例

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

出典

East Central North America 1998