Розпакування у GIF
Один із відомих методів стиснення файлів зображень — це кодування у форматі Graphics Interchange Format (GIF), розроблене компанією CompuServe у 1987 році. Ось спрощена версія цього методу, застосована до рядків з алфавітними символами. Основою цього стиснення є словник, який призначає числові коди (у цій задачі ми будемо використовувати десяткову систему) різним рядкам символів. Словник ініціалізується зіставленнями для символів або підрядків, які можуть з'явитися в рядку. Наприклад, якщо ми очікуємо всі 26 літер алфавіту, словник спочатку міститиме коди (A, 00), (B, 01), (C, 02), ..., (Z, 25). Якщо ми стискаємо дані ДНК, словник спочатку міститиме лише 4 записи: (A, 0), (T, 1), (G, 2) та (C, 3). Зверніть увагу, що довжина кожного початкового коду однакова для всіх записів (2 цифри в першому прикладі та 1 цифра в другому).
Алгоритм стиснення виконується наступним чином:
Знайдіть найдовший префікс нестислої частини рядка, який є в словнику, і замініть його на його числовий код.
Якщо кінець рядка не досягнуто, додайте нове зіставлення (s, n) до словника, де s = префікс, щойно стиснутий, плюс наступний символ після нього в рядку, а n = найменше число, яке ще не використане в словнику.
Наприклад, припустимо, що ми почали з рядка ABABBAABB і словника з лише двома записами, (A, 0) та (B, 1). Таблиця нижче показує кроки стиснення рядка.
Кінцевий стиснутий рядок — це 01234.
Є лише одне інше правило: рядки заміни, які використовуються, завжди мають розмір найдовшого коду в словнику на момент заміни. Таким чином, зі словником вище, якщо рядок для стиснення досить довгий, щоб у словник було додано запис виду (s, 10), то з цього моменту всі числові рядки заміни, що використовуються в стиснутому рядку, повинні бути розширені до 2 цифр (тобто A тепер буде кодуватися як 00, B як 01, AB як 02 і т.д.); якщо у словник додається запис (s′, 100), всі заміни з цього моменту будуть збільшені до 3 цифр, і так далі. Таким чином, довший рядок ABABBAABBAABAABAB буде закодовано як 01234027301, а не 0123402731. Спробуйте!
Добре, тепер, коли ви експерти в стисненні, час розслабитися і розпакувати!
Вхідні дані
Кожен тестовий випадок складатиметься з двох рядків. Перший рядок міститиме рядок цифр для розпакування. Другий рядок міститиме початковий словник, використаний у стисненні. Цей рядок починатиметься з додатного цілого числа n, що вказує на кількість записів у словнику (1 ≤ n ≤ 100), після чого йтимуть n алфавітних рядків. Перший з них буде зіставлений з 0 у словнику (або 00, якщо n > 10), другий з 1, і так далі. Останній тестовий випадок буде завершено рядком, що містить лише 0.
Вихідні дані
Для кожного тестового випадку виведіть один рядок, що містить номер випадку (використовуючи формат, показаний нижче) з наступним розпакованим рядком. Всі вхідні рядки були легально стиснуті.