Регулярні вирази 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, якщо такого не існує.