Сортування ДНК#1306
Однією з мір "невідсортованості" послідовності є кількість пар елементів, які розташовані не у правильному порядку один відносно одного. Наприклад, у послідовності "DAABEC" ця міра дорівнює , оскільки D перевищує чотири букви праворуч від неї, а E перевищує одну букву праворуч. Ця міра називається кількістю інверсій у послідовності. У послідовності "AACEDGG" є лише одна інверсія (E і D) — вона майже впорядкована, у той час як у послідовності "ZWQM" інверсій (вона максимально невпорядкована — повністю обернений порядок).
Вам необхідно впорядкувати задані послідовності ДНК (кожна складається лише з чотирьох букв A, C, G та T). Однак, сортувати їх потрібно не в алфавітному порядку, а за "упорядкованістю" — від "найбільш впорядкованої" до "найменш впорядкованої". Усі послідовності мають однакову довжину.
Перший рядок містить ціле число , далі йде порожній рядок, після якого слідують наборів даних. Між наборами даних також стоїть порожній рядок.
Перший рядок кожного набору містить два цілих числа: довжину послідовностей (0 < n \le 50) і кількість послідовностей (0 < m \le 100). Далі йде рядків, кожен з яких містить послідовність довжини .
Для кожного набору даних виведіть список вхідних послідовностей, впорядкованих від "найбільш впорядкованої" до "найменш впорядкованої". Якщо дві або більше послідовностей мають однакову впорядкованість, виводьте їх у тому ж порядку, як у вхідних даних.
Між відповідями для різних наборів даних виводьте порожній рядок.
Приклад 1