დნმ-ის სორტირება

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


მიმდევრობისდაულაგებლობისერთ-ერთი საზომი არის ისეთ ელემენტთა წყვილების რაოდენობა, რომლებიც ერთმანეთის მიმართ არასწორი წესრიგით დგანან. მაგალითად, ასოთა მიმდევრობაში “DAABEC”, ეს საზომი არის 5-ის ტოლი, რადგან D მეტია მის მარჯვნივ მდგომ ოთხ ასოზე, ხოლო ასო E მეტია მის მარჯვნივ მდებარე ერთ ასოზე. ეს საზომი არის ინვერსიების რაოდენობა მიმდევრობაში. მიმდევრობას "AACEDGG" აქვს მხოლოდ ერთი ინვერსია(E და D) და ის თითქმის სორტირებულია, ამავე დროს მიმდევრობას "ZWQM" აქვს 6 ინვერსია(ის საერთოდ არ არის სორტირებული).

თქვენ უნდა დაალაგოთ დნმ სტრიქონების მიმდევრობა(ისინი შედგებიან მხოლოდ ოთხი ასოსგან A, C, G, Т). მაგრამ სორტირება უნდა მოხდეს არა ანბანური, არამედ „დალაგებულობის“ წესრიგით, „მეტად სორტირებულიდან ნაკლებად სორტირებულამდე“. ყველა სტრიქონს გააჩნია ერთნაირი სიგრძე.

შესატანი მონაცემები: პირველი სტრიქონი შეიცავს მთელ რიცხვს t-ს (1<=t<=10), რომელსაც მოჰყვება ცარიელი სტრიქონი და 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 დაკოპირება