Регулярні вирази (Easy)#3181
Регулярний вираз — це вираз, який визначає множину рядків. У цій задачі регулярний вираз містить лише малі латинські літери - та спеціальні символи '?', '*' і '+'. Кожна літера відповідає самій собі в підрядках, що визначаються виразом. Спеціальний символ може з’являтися тільки після якоїсь літери і вказує на кількість повторень цієї літери:
Наприклад, "ac", "abc", "acc", "abcccc" і так далі відповідають регулярному виразу "ab?c+".
Для заданого рядка знайдіть підрядок, який відповідає заданому регулярному виразу. Якщо існує кілька таких підрядків, виведіть той, який починається найближче до початку вихідного рядка. Якщо таких також кілька, виберіть найдовший.
У першому рядку знаходиться число (1 \leq T \leq 100) — кількість тестів. Далі йдуть тестів. У першому рядку кожного тесту міститься рядок довжини (1 \leq L \leq 200). У наступному рядку задано ціле число (1 \leq n \leq 10) — кількість регулярних виразів. Далі йдуть рядків з регулярними виразами R_i (1 \leq |R_i| \leq 20), для кожного з яких потрібно знайти підрядок у .
Для кожного регулярного виразу виведіть відповідний підрядок, або , якщо відповідного підрядка у заданому рядку немає.
Приклад 1