Optimal Klaviatura#6841
Optimus Mobiles SMS mesajlarını dəstəkləyən mobil telefonlar istehsal edir. Bu telefonların 12 düyməli klaviaturası var və düymələr 1-dən 12-yə qədər nömrələnib. Hər bir düyməyə bir simvol sırası təyin olunub. Müəyyən bir düymənin simvol sırasındakı n-ci simvolu yazmaq üçün həmin düyməni n dəfə basmaq lazımdır. Optimus Mobiles, ümumi sözlər lüğətindən təsadüfi bir mətn yazmaq üçün orta yazma səylərinin (yəni, orta düymə basma sayının) minimal olması üçün simvol sıralarını düymələrə təyin etmə problemini həll etmək istəyir.
Daha dəqiq desək, {a, b, c, …, z, +, *, /, ?} simvollar dəstini Şəkil 2-də olduğu kimi etiket lentində çap olunmuş hesab edin. Lentini hər biri bir və ya daha çox simvol olan 12 hissəyə bölmək istəyirik. 12 etiket soldan sağa doğru 1-dən 12-yə qədər nömrələnib və bu ardıcıllıqla klaviatura düymələrinə təyin olunacaq.
Şəkil 2
Siz ümumi sözlər lüğəti üçün 11 kəsmə mövqeyini tapmaq üçün proqram yazmalısınız. Kəsmə mövqeləri lüğətdəki bütün ümumi sözlər üzərində orta düymə basma sayını minimallaşdırmalıdır. Çıxışınız 11 simvoldan ibarət bir sətir olmalıdır, bu sətirdəki i-ci simvol (i+1)-ci etiketin ilk simvoludur.
Birinci sətir bir tam ədəd t (1 ≤ t ≤ 10) ehtiva edir, test halların sayı. Hər bir test halı bir sətirlə başlayır, burada bir tam ədəd M (1 ≤ M ≤ 10000) var, test halında ümumi sözlərin sayı. Hər bir M sonrakı sətirdə bir ümumi söz var. Hər bir ümumi söz ən çox 30 simvoldan ibarətdir və {a, b, c, …, z, +, *, /, ?} əlifbasından simvollar ehtiva edir.
Çıxış hər bir test halı üçün bir sətir ehtiva edir, optimal kəsim sətirini ehtiva edir. Aydındır ki, bir neçə optimal kəsim sətiri ola bilər, buna görə də leksik qrafik sırada ən kiçik olan optimal kəsim sətirini çap edin.
Nümunə 1