Поиск по шаблону
Имеются шаблон P и текст T, состоящие из букв латинского алфавита (верхнего или нижнего регистра). Шаблон может содержать также знаки вопроса ('?'), квадратные и фигурные скобки, смысл которых описан ниже. Необходимо найти все вхождения шаблона P в текст T.
Каждая позиция в шаблоне P может быть занята:
буквой латинского алфавита ('a' - 'z', 'A' - 'Z')
символом '?', на месте которого может находиться любая буква
квадратными скобками [...], где на месте трех точек находится набор букв, которые могут находиться в текущей позиции
фигурными скобками {...}, где на месте трех точек находится набор букв, которые не могут находиться в текущей позиции
буквы в скобках могут повторяться, как например [asssa] или {kLLf}
Например, если шаблон P задается в виде A?[bcC]{De}, то первой буквой слова должна быть 'A', второй может быть любая буква, третьей - буква b, c или C, а четвертой любая буква кроме D или e.
Входные данные
Первая строка содержит количество тестов n. Каждый тест состоит из двух строк. Первая строка содержит шаблон P, содержащий не более 100 символов и 60 позиций. Вторая строка содержит текст, состоящий из не более чем 10^6 букв.
Выходные данные
Для каждого теста в отдельной строке вывести все позиции текста, с которых может начинаться шаблон, в возрастающем порядке (первый символ текста T находится в позиции '1'). Если шаблон P не встречается в тексте T, то следует вывести сообщение "no match". Между выводимыми позициями должен находиться один пробел, а в начале или в конце каждой строки должны отсутствовать лишние пробелы.