Suffix Array Yenidən Qurulması
Uzun bir gün yeni işinizdə keçdi. Bütün günü yeni işəgötürəniniz, GCPC ([G]lobal Suffix [C]ollecting and [P]rocessing [C]ollective) ilə işlədiyiniz ən vacib Suffix-Array məlumat strukturlarını optimallaşdırmaqla keçirdiniz. İş stansiyanızı söndürmək üzrə olduğunuz anda monitora baxıb dayanırsınız. Testinizin nəticəsi göstərir ki, vacib məlumatların böyük hissəsi korlanmış ola bilər. Təəssüf ki, şirkətin ehtiyat nüsxə serverləri dünən çökmüşdü və indi siz dəyərli Suffix-Array-ları məhv etmiş ola bilərsiniz.
Məlumatı yoxlayarkən, vəziyyətin daha pis ola bilməyəcəyini görürsünüz. Çoxlu suffixlər itmiş və qalanlar da zədələnmiş ola bilər. Bəzi hallarda hərflərin bir hissəsi təsadüfi hərflərlə əvəz olunmuşdur və bəzi hissələrdə proqramda istifadə etdiyiniz '*' simvolunu, yer tutucu simvolunu tapırsınız. Bu yer tutucu simvol istənilən ölçüdə bir alt sətiri əvəz etmişdir. Bundan əlavə, bəzi uyğunsuz sətirlər tapdınız ki, hansı versiyanın doğru olduğunu müəyyən etmək mümkün deyil. İndi yeganə ümidiniz bərpanın mümkün olmasına dua etməkdir.
Məlumat, suffixlərin başlanğıc mövqeyi ilə birlikdə bir siyahı şəklində verilir. Şirkətin ehtiyatında olan bütün məlumat dəstlərinin uzunluq siyahısı da hələ əlinizdədir. Əsas sətirləri bərpa etmək mümkündürmü? Əgər belədirsə, bu yeni Suffix-Array alqoritmlərindən birini işə salaraq tam məlumat dəstini yenidən bərpa etmək olar.
Giriş verilənləri
Hər test dəsti bir neçə test halından t (0 < t ≤ 100) ibarətdir. Test hallarının sayı girişin əvvəlində tək sətirdə verilir. Hər test halı aşağıdakı kimi tərtib olunur. Əvvəlcə, tək sətirdə, istənilən çıxış sətirinin uzunluğu l və (qismən zədələnmiş) suffixlərin sayı s (1 ≤ l ≤ 10000; 1 ≤ s ≤ 10000) verilir. Sonra s sətir gəlir, burada sətirdəki suffixin mövqeyi p və suffix verilir (1 ≤ p ≤ l). Suffix yalnız {a, ..., z, A, ..., Z, ., *} dəstindən olan simvolları ehtiva edəcəkdir ('.' xüsusi mənaya malik deyil). Suffixlər üçün verilən simvolların ümumi cəmi 250000-i keçməyəcəkdir.
Çıxış verilənləri
İtirilmiş giriş məlumatlarını bərpa etmək mümkün olduqda bərpa edilmiş cümləni çap edin, əks halda tək sətirdə "IMPOSSIBLE" yazın. Bizim halda, bərpa yalnız sətirdəki bir mövqedə mümkün simvollar dəsti dəqiq bir simvol ehtiva etdikdə mümkündür.