Регуляр ifadələr Hard
Regulyar ifadə, sətirlər çoxluğunu təsvir edən bir ifadədir. Bu məsələdə regulyar ifadələr kiçik latın hərfləri a–z və xüsusi simvollar '?', '*' və '+' ilə tərtib olunmuşdur. Hər bir hərf, təsvir olunan sətirlərdə özünə uyğun gəlir. Xüsusi simvol yalnız hərfdən sonra gələ bilər və bu hərfin təkrar 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 olanı çıxarın. Əgər belə də bir neçə varsa, onların ən uzununu çı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 S uzunluğu L (1 ≤ L ≤ 200) olan sətiri ehtiva edir. Növbəti sətir tam ədəd n (1 ≤ n ≤ 10) — regulyar ifadələrin sayını ehtiva edir. Sonrakı n sətir S içində alt sətirləri tapmaq üçün R_i (1 ≤ R_i ≤ 100) uzunluğunda n regulyar ifadəni ehtiva edir.
Çıxış verilənləri
Hər bir regulyar ifadə üçün uyğun gələn alt sətiri çıxarın, əgər belə bir şey yoxdursa -1 çıxarın.