SP7866 ADV04G1 - Regular expressions (Hard)

Regular expression is an expression which defines a set of strings. In this problem regular expression will contain only small latin letters a-z and special characters ‘?’, ‘\*’ и ‘+’. Each letter corresponds to itself in the defined strings. Special character can occur only after some letter and means the number of repetitions of the letter: CharacterRepetitions ?none or one \*none or more +one or more

The first line of input contains number T - the amount of test cases. The description of T test cases follows. The first line of each test case is the given string S of length L. Next line contains number n - the amount of regular expressions. Next n lines describe one regular expression Ri each for which you should find the matching substrings.

For each regular expression print the matching substring or -1 if there is no such substring in the given string.