Сортировка ДНК
Сортировка ДНК
Одной из мер "неупорядоченности" в последовательности является количество пар элементов, которые находятся в неправильном порядке по отношению друг к другу. Например, в последовательности букв "DAABEC", эта мера равна 5, так как D больше четырех букв справа, а Е больше одной буквы справа. Этой мерой является количество инверсий в последовательности. Последовательность "AACEDGG" имеет только одну инверсию (E и D) - она почти отсортированная, в то время как последовательность "ZWQM" имеет 6 инверсий (она полностью неотсортированная).
Вам следует отсортировать последовательность ДНК строк (они содержат только четыре буквы A, C, G, Т). Однако сортировку следует производить не в алфавитном порядке, а в порядке "упорядоченности", от "самых отсортированных" до "наименее отсортированных". Все строки имеют одинаковую длину.
Входные данные
Первая строка содержит целое число t, за которым следует пустая строка и t тестов. Между соседними тестами находится пустая строка.
Первая строка каждого теста содержит два целых числа: длину входных строк n (0 < n ≤ 50) и количество строк m (0 < m ≤ 100). Далее следуют m строк, каждая из которых имеет длину n.
Выходные данные
Для каждого теста вывести последовательность строк в порядке от "наиболее отсортированной" до "наименее отсортированной". Если две или более строки равны при указанной сортировке, то выводить их следует в том же порядке в каком они поступали на вход.
Между ответами на соседние тесты следует выводить пустую строку.
1 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT
CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA