Регулярні вирази (складна версія)#3182
Регулярні вирази — це вирази, що визначають множину рядків. У цій задачі регулярні вирази складаються з малих латинських літер – та спеціальних символів , і . Кожна літера відповідає самій собі в описуваних рядках. Спеціальний символ може з'являтися лише після літери і вказує на кількість повторень цієї літери:
Наприклад, рядки "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 100).
Для кожного регулярного виразу виведіть відповідний підрядок, або -1, якщо такого підрядка не існує.
Приклад 1