Search by template#2562
The pattern P and the text T consist of letters of the Latin alphabet (uppercase or lowercase). The pattern may also contain the question mark ('?'), square brackets, and curly braces, as explained below. Find all occurrences of the pattern P in the text T.
Each position in the pattern P may be occupied by:
a Latin letter ('a' - 'z', 'A' - 'Z')
the character '?', which stands for any letter
square brackets [...], where the letters inside are allowed at the current position
curly braces {...}, where the letters inside are not allowed at the current position
letters in brackets may repeat, e.g. [asssa] or {kLLf}
For example, if the pattern P is A?[bcC]{De}, then the first letter must be 'A', the second can be any letter, the third must be b, c, or C, and the fourth can be any letter except D or e.
The first line contains the number of tests . Each test consists of two lines. The first line contains the pattern P, containing no more than characters and positions. The second line contains the text, consisting of no more than 10^6 letters.
For each test, output on a separate line all starting positions in the text where the pattern matches, in increasing order (the first character of the text T is at position ). If the pattern P does not occur in the text T, print "no match". There must be a single space between each printed position, and no extra spaces at the beginning or end of each line.
Example 1