İfadə

Müntəzəm ifadələr, mətn axtarışı və sətir uyğunlaşdırılması zamanı güclü bir vasitədir. Bu məsələdə sadələşdirilmiş müntəzəm ifadələrdən istifadə edəcəyik:

• Boş sətir "" müntəzəm ifadədir və yalnız boş sətir ona uyğundur.

• Bir böyük hərf "c" müntəzəm ifadədir, yalnız bir hərfdən c ibarət olan sətir ona uyğundur.

• Nöqtə "." müntəzəm ifadədir. Hər hansı bir tək hərfdən ibarət olan sətir ona uyğundur.

• Alternasiya: əgər a və b müntəzəm ifadələrdirsə, onda "(a|b)" da müntəzəm ifadədir. Sətir s ona uyğundur, yalnız s a və ya b-yə uyğundursa.

• Konkatenasiya: əgər a və b müntəzəm ifadələrdirsə, onda "(ab)" da müntəzəm ifadədir. Sətir s ona yalnız s = xy, x a-ya və y b-yə uyğundursa uyğundur.

• Kleene ulduzu: əgər a müntəzəm ifadədirsə, onda "(a*)" da müntəzəm ifadədir. Sətir s ona yalnız s boşdursa və ya s = xy, x boş deyil və a-ya uyğundur və y (a*)-yə uyğundursa uyğundur. Başqa sözlə, s sıfır və ya daha çox a-ya uyğun olan sətirlərdən ibarətdir.

Möhtərizələri buraxmaq olar. Bu məsələdə Kleene ulduzu ən yüksək prioritetə malikdir, konkatenasiya orta prioritetə malikdir və alternasiya ən aşağı prioritetə malikdir. Yəni "abc*|de" ifadəsi "(ab(c*))|(de)" deməkdir.

Məsələn, "abcabcab" sətiri "a(bc|a)*ab" ifadəsinə uyğundur, amma "abcbab" sətiri uyğun deyil.

Siz verilmiş müntəzəm ifadəyə E uyğun gələn və verilmiş alt sətir S-ni ehtiva edən ən qısa sətiri tapmalısınız.

Giriş məlumatları

Birinci sətir müntəzəm ifadə E-ni ehtiva edir. İkinci sətir alt sətir S-ni ehtiva edir (1 ≤ |E|,|S| ≤ 10 000).

Sətir S böyük latın hərflərindən ibarətdir. İfadə E böyük latın hərflərindən və xüsusi simvollardan ibarətdir: nöqtə ('.'), möhtərizələr ('(' və ')'), boru ('|') və ulduzlar ('*').

Çıxış məlumatları

E-yə uyğun gələn və S-ni alt sətir kimi ehtiva edən ən qısa sətir T-ni çıxarın. Əgər belə bir sətir mövcud deyilsə, "No" çıxarın.

Sətir T yalnız böyük latın hərflərindən ibarət olmalıdır.