Asan Mütəmadi İfadələr
Regulyar ifadə, sətirlər çoxluğunu təsvir edən bir ifadədir. Bu məsələdə regulyar ifadələr böyük latın hərfləri a–z və xüsusi simvollar '?', '*' və '+' ilə qurulur. Hər bir hərf, təsvir olunan sətirlərdə özünə uyğun gəlir. Xüsusi simvol yalnız bir hərfdən sonra gələ bilər və bu hərfin təkrarlanma sayını göstərir:
Məsələn, "ab?c+" regulyar ifadəsinə uyğun gələn sətirlər "ac", "abc", "acc", "abcccc" və s. ola bilər.
Verilmiş sətirdə, verilmiş regulyar ifadəyə uyğun gələn alt sətiri tapın. Əgər bir neçə belə alt sətir varsa, ilkin sətirdə solda yerləşəni çıxarın. Əgər belə alt sətirlər də bir neçə varsa, onların ən uzunu çıxarın.
Giriş verilənləri
Birinci sətir T (1 ≤ T ≤ 100) — testlərin sayını ehtiva edir. Sonra T test gəlir. Hər testin birinci sətiri uzunluğu L (1 ≤ L ≤ 200) olan S sətirini ehtiva edir. Növbəti sətir tam ədəd n (1 ≤ n ≤ 10) — regulyar ifadələrin sayını ehtiva edir. Növbəti n sətir, S içində alt sətirləri tapmaq üçün istifadə olunacaq uzunluğu R_i (1 ≤ R_i ≤ 2) olan n regulyar ifadəni ehtiva edir.
Çıxış verilənləri
Hər bir regulyar ifadə üçün ona uyğun gələn alt sətiri çıxarın, əgər belə bir alt sətir yoxdursa, -1 çıxarın.