Asan Mütəmadi İfadələr#3181
Regulyar ifadə, simvollar çoxluğunu təyin edən ifadədir. Bu məsələdə regulyar ifadə yalnız kiçik latın hərfləri - və xüsusi '?', '*', və '+' simvollarını ehtiva edəcək. Hər bir hərf müəyyən olunan simvollar çoxluğunda özünə uyğun gəlir. Xüsusi simvol yalnız hər hansı bir hərfdən sonra gələ bilər və həmin hərfin neçə dəfə təkrarlandığını bildirir:
Məsələn, "ac", "abc", "acc", "abcccc" və sair kimi sətirlər "ab?c+" regulyar ifadəsinə uyğun gəlir.
Verilmiş sətirdə, göstərilən regulyar ifadəyə uyğun gələn alt-sətiri tapın. Əgər bir neçə belə alt-sətir varsa, daxil olan sətirdə ən soldakını çıxışa verin. Əgər hələ də bir neçə belə varsa, ən uzununu çıxışa verin.
Birinci sətirdə (1 \leq T \leq 100) — testlərin sayı verilir. Sonra isə test təsviri ard-arda verilir. Hər bir test üçün birinci sətirdə uzunluqlu sətir (1 \leq L \leq 200) verilir. Sonrakı sətirdə regulyar ifadələrin sayı olan (1 \leq n \leq 10) verilir. Sonrakı sətirdə isə tapılması tələb olunan regulyar ifadə R_i (1 \leq |R_i| \leq 20) təqdim olunur.
Hər bir regulyar ifadə üçün uyğun gələn alt-sətiri çıxışa verin, əgər belə bir alt-sətir yoxdursa, çap edin.
Nümunə 1