Kodu Sındırmaq
Yeni Dünya Üsyankar Kodlayıcılar Ansamblı (NWERC) adlı terror təşkilatı cəmiyyətimiz üçün təhlükə yaradır. Xoşbəxtlikdən, onların xəbərləşmələrini gizlicə ələ keçirməyi bacarmışıq. Lakin bir problem var: mesajları şifrələnmişdir.
Kəşfiyyat məlumatlarına əsasən, mesajları yalnız kiçik hərflərdən ibarətdir və Əsas Əlifba Permutasiya Kodu (BAPC) ilə şifrələnmişdir. Bu kodda hər bir hərf əlifbadan başqa bir (kiçik) hərflə (və ya bəlkə də eyni hərflə) əvəz olunur. Orijinal mesajdakı iki fərqli hərf şifrələndikdən sonra da fərqli qalır, bu da unikal deşifrəni mümkün edir. Məsələn, "hello" "ifmmp" və ya "holle" kimi şifrələnə bilər, amma "cnoiz" və ya "bgrrb" kimi ola bilməz.
Bu çoxlu imkanlar yaradır və kodu qırmaq üçün səylərimiz indiyə qədər nəticəsiz qalıb. Xoşbəxtlikdən, bir informator vasitəsilə deşifrə olunmuş bir mesaj D əldə etmişik. Müvafiq şifrələnmiş mesajı əldə etməmişik, amma əminik ki, o, ələ keçirdiyimiz şifrələnmiş mesajlar siyahısında mövcuddur.
Sizin vəzifəniz, orijinal mesaj D və şifrələnmiş mesajlar siyahısı verildikdə, hansı şifrələnmiş hərfin hansı deşifrə olunmuş hərfə aid olduğunu (şifrələnmiş mesajlardan birinin orijinal mesaja uyğun olduğunu fərz edərək) mümkün qədər müəyyən edən bir proqram yazmaqdır.
Bu, sonra yeni ələ keçirilmiş kodlanmış mesaj Xi mümkün qədər deşifrə etmək üçün istifadə edilməlidir. Xüsusilə, Xdəki hər bir hərf üçün onun nəyi təmsil etdiyi tam əminliklə müəyyən edilə bilənlər – ya birbaşa, ya da deduktiv olaraq – deşifrə olunmalıdır. Digər bütün hərflər sual işarəsi ilə əvəz olunmalıdır.
Qeyd edək ki, bir neçə mesaj Dyə uyğun gələ bilsə də, bəzi hərfləri deşifrə etmək hələ də mümkün ola bilər (məsələn, nümunə girişində üçüncü test halına baxın).
Giriş verilənləri
Birinci sətirdə bir müsbət ədəd: test hallarının sayı, ən çox 100. Bundan sonra hər test halı üçün:
bir sətirdə tək bir tam ədəd n (1 ≤ n ≤ 100): şifrələnmiş mesajların sayı.
n sətir, hər biri bir sətir M_i: şifrələnmiş mesajlar.
bir sətir, tək bir sətir D: deşifrə olunmuş mesaj, şifrələnmiş mesajlardan birinə uyğun olduğu fərz edilir.
bir sətir, tək bir sətir X: deşifrə olunacaq mesaj.
Bütün sətirlər ən azı 1 və ən çox 1000 kiçik hərfdən ibarətdir.
Çıxış verilənləri
Hər test halı üçün:
bir sətir, tək bir sətir Y. Xdəki hər hərf üçün, Ydəki müvafiq hərf deşifrə olunmuş qarşılığı olmalıdır, ya da bilinmirsə '?' olmalıdır. Əgər heç bir şifrələnmiş mesaj M_i Dnin şifrələnmiş versiyası ola bilməzsə, o zaman sətir "IMPOSSIBLE" olmalıdır.