Регулярные выражения Hard
Регулярным выражением называется выражение, описывающее множество строк. В данной задаче регулярные выражения состоят из прописных латинских букв a–z и специальных символов '?', '*' и '+'. Каждая буква соответствует самой себе в описываемых строках. Специальный символ может стоять только после какой-то буквы, и означает количество повторений этой буквы:
Символ Число повторений ? Ноль или одно * Ноль или более + Одно или более Например, регулярному выражению "ab?c+" соответствуют строки "ac", "abc", "acc", "abcccc", и т. д.
В заданной строке найдите подстроку, удовлетворяющую заданному регулярному выражению. Если таких несколько, то выведите то, которое находится левее в исходной строке. Если и таких несколько, то выведите самую длинную из них.
Входные данные
Первая строка содержит T (1 ≤ T ≤ 100) — количество тестов. Затем следует T тестов. Первая строка каждого теста содержит строку S длины L (1 ≤ L ≤ 200). Следующая строка содержит целое число n (1 ≤ n ≤ 10) — количество регулярных выражений. Следующие n строк содержат n регулярных выражений длины R[i] (1 ≤ R[i] ≤ 100), по которым надо найти подстроки в S.
Для каждого регулярного выражения выведите соответствующую ему подстроку, или -1, если такой не существует.