// trie.cpp (Uklada telefonni seznam do pismenkoveho stromu (trie) a pak v nem vyhledava.)
// author: Acris

#include "stdafx.h"
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


class Nod {
public:
    int znak;
    string cislo;
    vector<Nod*> deti;
    Nod() {
        for(int i= 0; i <= 26; i++) {
            deti.push_back(0);
        }
        cislo = "-";
    }
    Nod(string telefon, int pismeno) {
        cislo = telefon;
        znak = pismeno;
        for(int i= 0; i <= 26; i++) {
            deti.push_back(0);
        }
    }
    ~Nod() {
        for(int i= 0; i <= 26; i++) {
            delete deti[i];
        }
    }
    void pridejCislo(string telefon) {
        cislo = telefon;
    }
};

Nod* root;


int Znak(char c) {
    int aktZnak;
    if ( c == ' ') aktZnak = 26;
    else {
        if ( islower(c) ) {
        c = toupper(c);
        }
        aktZnak = (int)c - 'A';
    }
    return aktZnak;
}

char NaZnak(int x) {
    char c;
    if ( x == 26 ) c = ' ';
    else c = (char)(x + 'A');
    return c;
}

void Vloz(const string& jmeno, const string& tel) {
    int i=0;
    int aktZnak = Znak( jmeno.at(i) );
    Nod* akt = root;
    while ( i < jmeno.size() ) {
        aktZnak = Znak( jmeno.at(i) );
        if ( (*akt).deti.at(aktZnak) == 0 ) {
            (*akt).deti.at(aktZnak) = new Nod();
        }
        akt = (*akt).deti.at(aktZnak);
        i++;
    }
    (*akt).cislo = tel;
}

Nod* Najdi(const string& jmeno) { //vraci 0, pokud tam neni
    int i=0;
    int aktZnak = Znak( jmeno.at(i) );
    Nod* akt = root;
    while ( i < jmeno.size() ) {
        aktZnak = Znak( jmeno.at(i) );
        if ( (*akt).deti.at(aktZnak) == 0 ) {
            cout << "Neni zaznam. " << endl;
            return 0;
        }
        akt = (*akt).deti.at(aktZnak);
        i++;
    }
    return akt;
}


void VypisPrefix( const string& prefix) {
    bool velke = true;
    for(int i=0; i < prefix.size(); i++) {
        if ( !velke && (prefix.at(i) != ' ') ) cout << (char)tolower(prefix.at(i));
        else cout << prefix.at(i);
        if ( prefix.at(i) == ' ' )
            velke = true;
        else
            velke = false;
    }
}

void Vypis(Nod* akt, string prefix) {
    if ((*akt).cislo != "-" ) {
        VypisPrefix(prefix);
        cout << "|" << (*akt).cislo << endl;
    }
    for(int i=0; i<= 26; i++) {
        if ( (*akt).deti.at(i) != 0 )
            Vypis( (*akt).deti.at(i), prefix + (NaZnak(i)) );
    }
}

void Hledej(const string& prefix) {
    Nod* muj = Najdi(prefix);
    if (muj != 0) Vypis(muj, prefix);
}

string Zpracuj(const string& retez) {
    string novy;
    for(int i=0; i< retez.size(); i++) {
        novy.push_back(toupper(retez.at(i)));
    }
    return novy;
}

int _tmain(int argc, _TCHAR* argv[])
{
    root = new Nod("-",'-');

    /*Vloz("A","252");
    Vloz("AB","2526");
    Vloz("AC","25265");
    Vloz("D","1526");
    Vloz("ADC","2526");*/

    //if (root != 0) Vypis(root, "");

    /*Nod* muj = Najdi("AC");
    if (muj != 0) cout << (*muj).cislo << endl;*/

    //Hledej("A");

    ifstream ifs("input.txt");
    string radka;
    while ( getline(ifs, radka) ) {
        string::iterator b,e;
        b = radka.begin();
        e = find( b, radka.end(), '|');
        string jmeno(b,e);
        b = ++e;
        string tel(b,radka.end());
        cout << jmeno << "|" << tel <<endl;
        Vloz(jmeno, tel);
    }
    ifs.close();

    while ( getline(cin, radka) ) {
        if ( radka == "" ) continue;
        if ( radka == "#KONEC") break;
        radka = Zpracuj(radka);
        Hledej(radka);
    }
    
    delete root;
    return 0;
}