მინიმალური სტრინგი

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

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

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

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

წყარო: USACO, 2007/08, DEC, GOLD


მოცემულია N (1 <= N <= 30,000) სიმბოლოსაგან შედგენილი მწკრივი. თითოული სიმბოლო წარმოადგენს ლათინური ანბანის ერთ-ერთი ასოს A-დან Z-ის ჩათვლით (ზედა რეგისტრში). თქვენ შეგიძლიათ აარჩიოთ სიმბოლო მწკრივის ნებისმიერი ბოლოდან და ჩასვათ სტრინგის ბოლოში. მოყვანილი წესით მიიღეთ ლექსიკოგრაფიულად მინიმალური სტრინგი.

შემავალი მონაცემების ფორმატი :

* სტრიქონი 1: ერთი მთელი რიცხვი N;

* სტრიქონები 2..N+1: ხაზი i+1 შეიცავს თითო ასოს ('A'..'Z') - მწკრივის სიმბოლოებს.

 

გამომავალი მონაცემების ფორმატი :

ლექსიკოგრაფიულად უმცირესი სტრიქონი, რაც შეიძლება მივიღოთ სიმბოლოების გადალაგების მოცემული წესით. თითო ხაზში, შესაძლებელია ბოლო ხაზის გარდა, ამობეჭდეთ 80 სიმბოლო.




მაგალითები

შესატანი მონაცემები
6 A C D B C B დაკოპირება
გამოსატანი მონაცემები
ABCBCD დაკოპირება

შენიშვნა

განმარტება:

მოქმ. საწყისი l ახალი

#1 ACDBCB

#2 CDBCB      A

#3 CDBC       AB

#4 CDB         ABC

#5 CD           ABCB

#6 D             ABCBC

#7                ABCBCD