eolymp
bolt
Try our new interface for solving problems
Problems

Regular expressions (Hard)

Regular expressions (Hard)

Time limit 1 second
Memory limit 64 MiB

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 '?', '*' and '+'. 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:

For example "ac", "abc", "acc", "abcccc", and so on match regular expression "ab?c+". For the given string find the substring which matches the given regular expression. If there are many such substrings find the most left one. If there are many of those as well fing the longest one.

Input data

The first line of input contains number T (1T100) — 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 (1L200). Next line contains number n (1n10) — the amount of regular expressions. Next n lines describe one regular expression R_i (1R_i100), each for which you should find the matching substrings.

Output data

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

Examples

Input example #1
1
aabbcc
5
b*c
a?b+c+
ab?c
b?c?
a?b?c?
Output example #1
bbc
abbcc
-1

a