#include <iostream>
#include <string>
#include <vector>
#include <Windows.h>
#include <algorithm>

using namespace std;

struct myMap {
    std::string key;
    std::string value;
};

bool myComp(const myMap &a, const myMap &b) {
    return a.key.length() > b.key.length();
}

int main() {
    /*setlocale(LC_ALL, "ru_RU");*/
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);

    int count_el, count_str;
    cin >> count_el >> count_str;
    vector<myMap> mp(count_el);
    string a;
    getline(cin, a);

    for (int i = 0; i < count_el; i++) {
        getline(cin, mp[i].key);
        getline(cin, mp[i].value);

    }
    sort(mp.begin(), mp.end(), myComp);
    string main_str;


    for (int i = 0; i < count_str + 1; i++) {
        string tmp;
        getline(cin, tmp);
        main_str += tmp + '\n';
    }

    for (int i = 0; i < mp.size(); i++) {
        int left;
        cout << mp[i].key << '\n';
        do {
            left = main_str.find(mp[i].key);
            if (left != -1) {
                main_str.replace(left, mp[i].key.length(), (string) mp[i].value);
            }
        } while (left != -1);


    }

    cout << main_str;
}