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 ‘?’, ‘*’ 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:

CharacterRepetitions
?none or one
*none or more
+one or more

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

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.

Constraints

1 <= T <= 100
1 <= n <= 10
1 <= L <= 200
1 <= Ri <= 100

Output

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

Example

Input:
1
aabbcc
5
b*c
a?b+c+
ab?c
b?c?
a?b?c?

Output:
bbc
abbcc
-1

a


Added by:Spooky
Date:2010-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 PERL6 TCL
Resource:Advancement Autumn 2010, http://sevolymp.uuuq.com/, author: Alexey Shchepin

hide comments
2020-04-29 14:46:11 Simes
For another regex problem, see PATT.
2011-08-31 12:25:01 nt_d2
Please tell me what was wrong with my submission (ID: 5587144). I've written hundreds of cases but still couldn't find out how I got WA

Edit: Now I know my mistake, I treated empty string as the left most string (which is not). Should have seen it from the beginning :)

Last edit: 2011-09-03 07:03:26
2010-12-15 10:24:11 [Rampage] Blue.Mary
The length of the input string L will be less than 200 I think.

edit: indeed... updated...

Last edit: 2010-12-15 10:26:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.