Montaj xətti
Sonuncu işçi Avtomatlaşdırılmış Maşınlar Fabrikindəki istehsal xəttində narahatdır. O, məhsuldarlığını artırmasa, işini itirəcəyindən qorxur. Onun işi müəyyən ardıcıllıqla parçaları yığmaqdan ibarətdir. Lakin a və b, sonra c parçalarını yığmaq üçün sərf olunan vaxt, b və c parçalarını yığmaq və sonra alınan komponentlə a-nı yığmaq üçün sərf olunan vaxtla eyni olmaya bilər. Eyni anda yalnız iki ardıcıl parça yığıla bilər və onlar yığıldıqdan sonra, sonrakı yığım üçün lazım olan vaxt baxımından başqa bir parça kimi davranırlar.
Ona kömək etmək üçün bütün komponentləri yığmaq üçün optimal yolu tapmalısınız. Proqramınıza giriş, parçaları təmsil edən simvollar dəsti və onları yığmaq üçün lazım olan vaxtı, eləcə də alınan komponentin növünü göstərən yığım cədvəli olacaq. Məsələn, bizdə iki simvol {a, b} və aşağıdakı cədvəl ola bilər:
Bu o deməkdir ki, məsələn, a tipli iki parça 3 dəqiqə ərzində yığıla bilər və nəticə b tipli bir komponentdir, yəni onu, məsələn, a tipli başqa bir parçayla yenidən yığmaq üçün tələb olunan vaxt 6 dəqiqədir və s. Qeyd edək ki, cədvəl simmetrik deyil, yəni b və a-nı yığmaq a və b-ni yığmaqdan daha çox vaxt apara bilər.
aba etiketli komponentlər ardıcıllığı üçün iki mümkün həll var:
(ab)a = ba = a ilə vaxt time(ab) + time(ba) = 5 + 6 = 11.
a(ba) = aa = b ilə vaxt time(ba) + time(aa) = 6 + 3 = 9.
Beləliklə, bu halda nəticə 9 dəqiqə ərzində b tipli bir parça olacaq (9-b ilə göstərilir).
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Hər bir test halı təbii ədəd k (1 ≤ k ≤ 26) olan bir sətirlə başlayır, ardınca boşluqla ayrılmış k simvolu (simvollar [a-z] arasında) olan bir sətir gəlir. Sonrakı k sətir yığım cədvəlini ehtiva edir: i-ci sətirdə k cütlük var, hər biri time- result formasında, burada time 0 ilə 1 000 000 arasında olan tam ədəddir və result əvvəlki dəstəyə aid olan bir simvoldur. i-ci sətirdəki j-ci cütlük, i-ci və j-ci simvollarla təmsil olunan parçaları yığmaq üçün vaxtı və alınan parçanın növünü göstərir. Cədvəldən sonra bir sətir, ardınca gələn sətirlərin sayını göstərən n tam ədədini ehtiva edir, hər sətir ən çox 200 simvoldan ibarət bir sətirdir. Bu sətirlərin hər biri düzgün ardıcıllıqla yığılmalı olan komponentlər ardıcıllığıdır.
Giriş '0' olan bir sətirlə bitəcək, bu işlənməməlidir.
Çıxış verilənləri
Hər bir test halı üçün n sətir çap edin, hər biri time- result formatında bir tam vaxt və bir simvol nəticəsi ilə. Hər sətir girişdəki müvafiq hal üçün minimum vaxtı və alınan parçanın növünü təmsil edir. Əgər eyni minimum vaxtla bir neçə mümkün nəticə arasında bərabərlik varsa, test halının əvvəlindəki k simvolları ehtiva edən sətirdə ilk görünən parçanın növünü seçin. (Məsələn, əgər həmin sətir a c b idisə və həm c, həm də b minimum cost5 ilə əldə edilə bilərsə, 5-c çap edin).
Fərqli test hallarının çıxışları arasında boş sətir olmalıdır.