eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Регулярні вирази Easy

Регулярні вирази Easy

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Регулярним виразом називається вираз, який описує множину рядків. У даній задачі регулярні вирази складаються з прописних латинських літер az та спеціальних символів '?', '*' та '+'. Кожна літера відповідає сама собі у рядках, що описуються. Спеціальний символ може стояти лише після якоїсь літири і позначає кількість повторень цієї літери:

Наприклад, регулярному виразу "ab?c+" відповідають рядки "ac", "abc", "acc", "abcccc", и т. д.

У заданому рядку знайдіть підрядок, який задовільняє заданому регулярному виразу. Якщо таких декілька, то виведіть той, який знаходиться лівіше у початкову рядку. Якщо і таких декілька, то виведіть самий довгий з них.

Вхідні дані

Перший рядок містить T (1T100) — кількість тестів. Далі йде T тестів. Перший рядок кожного тесту містить рядок S довжини L (1L200). Наступний рядок містить ціле число n (1n10) — кількість регулярних виразів. Наступні n рядків містять n регулярних виразів довжини R_i (1R_i2), за якими потрібно знайти підрядки в S.

Вихідні дані

Для кожного регулярного виразу виведіть відповідний йому підрядок, або -1, якщо такого не існує.

Приклад

Вхідні дані #1
1
aabbcc
5
ab
c+
ac
b*
a?
Вихідні дані #1
ab
cc
-1

a