Hesablama Cədvəlləri
Telekommunikasiya sahəsində müxtəlif telefon nömrələrinə edilən zənglər fərqli tariflər və ya ödəniş planları ilə hesablanmalıdır. Beynəlxalq Telefon Rabitəsi Daşıyıcısı (ICPC) hansı telefon zənginin hansı ödəniş planı ilə hesablanacağını müəyyən edən köhnə bir ödəniş cədvəlinə malikdir.
Hər bir beynəlxalq telefon nömrəsi 11 rəqəmdən ibarətdir. Ödəniş cədvəli n sətirdən ibarətdir. Hər sətir telefon nömrələrinin prefiks diapazonunu göstərir, məsələn, "7919 - 921". Bu spesifikasiya 7919, 7920 və 7921 ilə başlayan bütün telefon nömrələrinin bu sətirlə uyğun olduğunu bildirir. Hər prefiks üçün ödəniş planı adı göstərilir. Zəng üçün ödəniş planını müəyyən etmək üçün cədvəl yuxarıdan aşağıya doğru skan edilir və ilk uyğun sətir ödəniş planını müəyyən edir. Əgər heç bir uyğunluq tapılmazsa, telefon nömrəsi etibarsızdır və ödəniş planı tələb olunmur. Xüsusi bir ödəniş planı olan "invalid" (tırnaq işarələri olmadan) etibarsız telefon nömrələrini alternativ şəkildə müəyyən etmək üçün istifadə olunur. Bəzi ödəniş planları tamamilə fərqli görünən telefon nömrələri üçün istifadə olunur və onların adları cədvəlin müxtəlif yerlərində müxtəlif sətirlərdə göstərilə bilər.
ICPC-nin ödəniş cədvəli köhnədir və bir çox qeydlər ehtiva edir. Bu qeydlərin bəziləri artıq istifadə olunmaya bilər. Hər bir ödəniş planının əslində hansı telefon nömrələri üçün istifadə olunduğunu anlamaq çox çətindir. ICPC rəhbərliyi bu ödəniş cədvəlini daha oxunaqlı formata çevirmək qərarına gəlib. Bu yeni formatda cədvəl sadə prefikslərin leksikoqrafik olaraq sıralanmış siyahısından ibarət olacaq (köhnə formatın "-" diapazon xüsusiyyəti olmadan) və hər prefiks üçün bir ödəniş planı adı olacaq. Yeni ödəniş cədvəlindəki heç bir prefiks cədvəldəki digər prefikslərin prefiksi olmamalıdır. Beləliklə, sadə bir lüğət axtarışı (məsələn, ikili axtarış) verilmiş telefon nömrəsi üçün ödəniş planını müəyyən etmək üçün kifayət edəcək. Verilmiş ödəniş planı üçün bütün telefon nömrələrini tapmaq da çox sadə bir iş olacaq. Yeni ödəniş cədvəlindəki sətirlərin sayı minimuma endirilməlidir. "invalid" adlı ödəniş planı yeni ödəniş cədvəlində ümumiyyətlə olmamalıdır, çünki etibarsız telefon nömrələri yeni ödəniş cədvəlində müvafiq prefiksin olmaması ilə göstəriləcək.
Giriş verilənləri
Girişin ilk sətri köhnə ödəniş cədvəlindəki sətirlərin sayını göstərən tək tam ədəd n (1 ≤ n ≤ 100) ehtiva edir. Sonrakı n sətir köhnə ödəniş cədvəlini hər sətirdə bir qayda ilə təsvir edir. Hər qayda dörd boşluqla ayrılmış token ehtiva edir — prefiks A, minus işarəsi ("-"), prefiks B və ödəniş planı adı. Prefikslər hər biri 1 ilə 11 rəqəm arasında, ödəniş planı adı isə 1 ilə 20 kiçik hərf arasında ehtiva edir.
Daha sonra, |A| ilə prefiks A-nın rəqəmlərinin sayını göstərək. 1 ≤ |B| ≤ |A| ≤ 11 olduğu doğrudur. Üstəlik, prefiks A-nın son |B| rəqəmləri leksikoqrafik olaraq B-yə bərabər və ya ondan əvvəl gələn bir sətir təşkil edir.
Belə bir prefiks cütü A və B ilk |A| – |B| rəqəmləri A-nın ilk rəqəmləri ilə uyğun olan və sonrakı |B| rəqəmləri A-nın son |B| rəqəmləri ilə B arasında leksikoqrafik olaraq olan (daxil olmaqla) bütün telefon nömrələrinə uyğun gəlir.
Çıxış verilənləri
Çıxışa verilmiş köhnə ödəniş cədvəlini təsvir etmək üçün yeni cədvəlin ehtiva etməli olduğu minimal sətir sayını göstərən tək tam ədəd k yazın. Sonra leksikoqrafik olaraq sıralanmış yeni ödəniş cədvəlini k sətir yazın. Hər sətirdə boşluqla ayrılmış iki token yazın — prefiks və ödəniş planı adı. Qeyd edək ki, yeni ödəniş cədvəlindəki prefiks ən azı bir rəqəm ehtiva etməlidir.
Əgər bütün telefon nömrələri etibarsızdırsa (hər telefon nömrəsi uyğun sətirə malik deyil və ya "invalid" ödəniş planı ilə uyğun gəlirsə), çıxış yalnız sıfır rəqəmi ehtiva etməlidir.