Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3927.   Search by template
Time Limit: 3.0 Seconds   Memory Limit: 65536K
Total Runs: 26   Accepted Runs: 9

The pattern P and the text T are given. They contain the letters of the Latin alphabet (lowercase and uppercase). The pattern may also contain the characters '?', '[', ']', '{' and '}' You must find all the positions where P appears in T. Each position in the pattern P may contain:

1.a letter from the Latin alphabet ('a' – 'z', 'A' – 'Z')

2.the character '?' that can replace any letter (on its place can be any letter)

3.brackets '['...']', between them there is the set of letters that may be in the

current position

4.brackets '{'...'}', between them there is the set of letters that are not allowed

to be in the current position

5.the letters can be repeated in brackets like [asssa] or {kLLf}.

For example, if the pattern P is A?[bcCc]{De}, then the first letter of a match must be A, the second can be any Latin letter, the third - letter b, c or C, and the fourth can be any Latin letter except D or e.

Input

The first line contains the number of test cases n. Each test consists of two lines. The first line contains the pattern P with no more than 100 characters and 60 positions. The second line contains the text with no more than 106 letters.

Output

For each test case print on a separate line all text positions where the pattern matches, in ascending order (the first letter from the text T is assumed to have the position ‘1’). If the pattern P does not appear in text T, print the message "no match". There must be a single space between each printed position, and no extra space at the beginning/end of line.

Sample Input

3
A?[bcCc]{De}
yAqCpsApbeAocqq
???[QWERTY]
aSdFrQererRTY
{eRT}?
eRTeRTq


Sample Output

2 11
3 8 9 10
no match


Source: Southeastern European Regional Programming Contest Bucharest,Romania,2011
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz