ADV04G - Regular expressions (Easy)

no tags 

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

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 <= 2

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
ab
c+
ac
b*
a?

Output:
ab
cc
-1

a


hide comments
Simes: 2020-04-29 14:46:50

For the harder version of this problem, see ADV04G1.

Last edit: 2020-04-29 14:49:51
sarasouju: 2010-12-15 10:25:08

Last edit: 2010-12-06 06:27:04
.::Manish Kumar::.: 2010-12-15 10:25:08

This problem is good enough for classical :)


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