/*
TASK:wac
LANG:C++
*/

#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

#include "module.h"

#define IN "wac.in"
#define OUT "wac.out"
#define X first
#define Y second
#define mp make_pair
#define MAXW 100100

char words[MAXW][32] = {};

typedef struct node {
        int w;
        int id;
        node () {w = id = 0;}
        node (int ww,int iid) {
             w = ww,id = iid;
        }

        bool operator < (const node & h) const {
             if (strcmp(words[id],words[h.id]) > 0)
                return false;
             else return true;
        }
};




char str[128],q[128] = {};


map<string,pair<int,string> > m;

set<node> s;
set<node>::iterator it1,it2,oldit1;

int Wfree = 1;

int best,prev;

int find () {
    do {
       if ( (*it1).id > prev && (*it1).id < best) {
          best = (*it1).id;
       }
       it1++;
    } while (it1 != it2);
    return 0;
}

int output() {
    printf("%d - ",s.size());
    for (set<node>::iterator it = s.begin(); it != s.end(); it++) {
        printf("%d %s ",(*it).id,words[(*it).id]);
    }
    printf("\n");
    
    return 0;
}

int main () {
    init();

    char temp[128];
    char temp1[128];
    
    while (1) {
    
       getQuery(q);
       
       if (q[0] == 'A') {
          sscanf(q,"%s %s",temp,str);
          strcpy(words[Wfree],str);
          s.insert(node(Wfree,Wfree));
          Wfree++;
       }
       if (q[0] == 'F') {
          sscanf(q,"%s %s %s",temp,temp1,words[0]);
          it1 = lower_bound(s.begin(),s.end(),node(0,0));
          int l = strlen(words[0]);
          words[0][l] = '}';
          words[0][l+1] = 0;
          it2 = lower_bound(s.begin(),s.end(),node(0,0));
          words[0][l] = 0;
          
          best = MAXW;
          
          prev = 0;
          if (it1 == it2) {
             m[temp1] = make_pair(best,string(words[0]));
             answerQuery(".");
             continue;
          }
          oldit1 = it1;
          find();
          if (best == MAXW) {
             prev = 0;
             it1 = oldit1;
             find();
          }
          m[temp1] = make_pair(best,string(words[0]));
          answerQuery(words[best]);
       }
       
       if (q[0] == 'N') {
          sscanf(q,"%s %s",temp,temp1);

          string ss = m[temp1].Y;
          strcpy(words[0],ss.c_str());
          
          it1 = lower_bound(s.begin(),s.end(),node(0,0));
          int l = strlen(words[0]);
          words[0][l] = '}';
          words[0][l+1] = 0;
          it2 = lower_bound(s.begin(),s.end(),node(0,0));
          words[0][l] = 0;
          
          best = MAXW;
          prev = m[temp1].X;
          if (it1 == it2) {
             answerQuery(".");
             continue;
          }
          oldit1 = it1;
          find();
          if (best == MAXW) {
             prev = 0;
             it1 = oldit1;
             find();
          }
          m[temp1] = make_pair(best,string(words[0]));
          answerQuery(words[best]);
       }
    }

    return 0;
}
