Расслабление в формате 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.
Выходные данные
Для каждого тестового случая выведите одну строку, содержащую номер случая (используя формат, показанный ниже), за которым следует декомпрессированная строка. Все входные строки были легально сжаты.