Задачі
Регулярні вирази Hard
Регулярні вирази Hard
Регулярним виразом називається вираз, який описує множину рядків. У даній задачі регулярні вирази складаються з прописних латинських літер \textbf{a}--\textbf{z} та спеціальних символів '\textbf{?}', '\textbf{*}' та '\textbf{+}'. Кожна літера відповідає сама собі у рядках, що описуються. Спеціальний символ може стояти лише після якоїсь літири і позначає кількість повторень цієї літери:
Наприклад, регулярному виразу "\textbf{ab?c+}" відповідають рядки "\textbf{ac}", "\textbf{abc}", "\textbf{acc}", "\textbf{abcccc}", и т. д.
У заданому рядку знайдіть підрядок, який задовільняє заданому регулярному виразу. Якщо таких декілька, то виведіть той, який знаходиться лівіше у початкову рядку. Якщо і таких декілька, то виведіть самий довгий з них.
\InputFile
Перший рядок містить \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{100}) --- кількість тестів. Далі йде \textbf{T} тестів. Перший рядок кожного тесту містить рядок \textbf{S} довжини \textbf{L} (\textbf{1} ≤ \textbf{L} ≤ \textbf{200}). Наступний рядок містить ціле число \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10}) --- кількість регулярних виразів. Наступні \textbf{n} рядків містять \textbf{n} регулярних виразів довжини \textbf{R_i} (\textbf{1} ≤ \textbf{R_i} ≤ \textbf{100}), за якими потрібно знайти підрядки в \textbf{S}.
\OutputFile
Для кожного регулярного виразу виведіть відповідний йому підрядок, або \textbf{-1}, якщо такого не існує.
Вхідні дані #1
1 aabbcc 5 b*c a?b+c+ ab?c b?c? a?b?c?
Вихідні дані #1
bbc abbcc -1 a