Parti Oyunları#6215
Siz bir məclisə dəvət olunmusunuz. Ev sahibi, məclis oyunları üçün qonaqları 2 komandaya bölmək istəyir və hər komandada tam olaraq eyni sayda qonaq olmalıdır. O, qonaqları qarşılayarkən onların hansı komandada olduğunu asanlıqla müəyyən etmək istəyir, hər qonağın adını siyahıda axtarmağa vaxt sərf etmədən. Yaxşı bir kompüter mütəxəssisi olaraq, sizin bir fikriniz var: ona tək bir sətir verin və o, yalnız qonağın adının bu sətirdən əlifba sırasına görə kiçik və ya böyük olduğunu müəyyən etməlidir.
n məclis qonağının unikal adları verildikdə (n cütdür), elə ən qısa mümkün S sətirini tapın ki, dəqiq yarısı S-dən kiçik və ya bərabər, digər yarısı isə S-dən böyük olsun. Əgər ən qısa uzunluqda bir neçə sətir varsa, əlifba sırasına görə birinci olanı çıxarın.
Girişdə bir neçə test halı olacaq. Hər test halı öz sətirində cüt tam ədəd n (2 ≤ n ≤ 1000) ilə başlayacaq. Növbəti n sətirdə adlar olacaq, hər sətirdə bir ad. Hər ad yalnız böyük hərflərlə yazılmış bir söz olacaq və ən azı bir hərfdən ibarət olacaq, ən çox isə 30 hərf olacaq. Bir test halındakı bütün adlar unikal olacaq. Giriş 0 ilə bitəcək.
Hər hal üçün ev sahibinin qonaqları ayırmaq üçün istifadə edə biləcəyi ən qısa mümkün sətirlərdən əlifba sırasına görə birincisini çıxarın. Bu sətiri bütün böyük hərflərlə yazın. Heç bir boşluq çıxarmayın. Çıxışlar arasında boş sətir qoymayın.
Nümunə 1