#include <bits/stdc++.h>
#define C (*s - 'a')

using namespace std;

std::fstream fin;

struct trie{
    int wo,pf;
    trie *edge[32];
    char adres[32];
    trie(){
        wo = pf = 0;
        memset (edge,0,sizeof( edge ));
    }

};

trie *T = new trie;


void Edit(char S[32],char *W,char *A,int i){
    for(i; S[i] != '\000' && !isdigit(S[i]) ;i++){
        if(i == ' ') continue;
        if(S[i] >= 'A' && S[i] <= 'Z')
            S[i] += 32;
        if(isalpha(S[i]))
            *W++ = S[i];
    }
    for(i; S[i] != '\000' && (isdigit(S[i]) || isalpha(S[i]));i++){

        *A++ = S[i];
    }
}



void Addw(trie *nod, char *s,char A[32]){
    if(*s == '\000'){
        nod ->wo ++;
        strcpy(nod -> adres,A);
        return;
    }
    if(nod -> edge[C] == 0){
        nod -> edge[C] = new trie;
        nod -> pf ++;
    }
    Addw(nod ->edge[C], s + 1,A);
}

int Deletew(trie *nod,char *s){
     if(*s == '\000'){
        memset(nod ->adres,sizeof(nod ->adres),0);
        nod ->wo--;
    } else if(nod -> edge[C] != 0  && Deletew(nod ->edge[C],s + 1)){
        nod ->edge[C] = 0;
        nod ->pf --;
    }
    if(nod->wo == 0 && nod ->pf == 0 && nod != T){
        delete nod; return 1;
    }
    return 0;
}

void Queryw(trie *nod,char *s,char A[32]){
    if(*s == '\000'){
        strcpy(A,nod ->adres);
        return;
     }
    if(nod ->edge[C])
        Queryw(nod ->edge[C], s + 1,A);
    return ;
}

void Updateinput(trie *nod,char *W,char *B){
    if(nod ->wo != 0){
        for(char *E = B; E != W; E++)
            fin << *E ;

        fin << "  " << nod -> adres <<"\n";
    }

    for(int i = 0; i < 32; i++){
        if(nod -> edge[i] != 0){
            *W = 'a' + i;
            Updateinput(nod -> edge[i],W + 1,B);
        }
    }
    return ;
}



int main()
{

    fin.open("input", std::fstream::in);

    ios :: sync_with_stdio(false);
    char S[32],W[32],A[32];
    while(fin.getline(S,sizeof(S))){
        memset(W,0,sizeof (W));
        memset(A,0,sizeof (A));
        Edit(S,W,A,0);
        Addw(T,W,A);
    }
    cout << "0 : Inserare element " << "\n" << "1 : Cauta adresa" << "\n" << "2 : Sterge element " << "\n" << "3 : Exist" << "\n";
    while(cin.getline (S,sizeof(S))){

        memset(W,0,sizeof (W));
        memset(A,0,sizeof (A));
        Edit(S,W,A,1);

        if(S[0] == '0')
            Addw(T,W,A);

        if(S[0] == '1'){
            memset(A,0,sizeof (A));
           Queryw(T,W,A);
           if(isdigit(A[0]))
                cout << "Adresa dorita este :" << A << "\n";
            else
                cout << "Nu a fost gasit!" << "\n";
           }

        if(S[0] == '2')
            Deletew(T,W);

         system("cls");

         if(S[0] == '3'){
            break;
         }


        cout << "0 : Inserare element " << "\n" << "1 : Cauta adresa" << "\n" << "2 : Sterge element " << "\n" << "3 : Exist" << "\n";

    }
    fin.close();
    fin.open("input", std::fstream::out | std::fstream::trunc);


    memset(W,0,sizeof (W));
    Updateinput(T,W,W);

    return 0;
}