{
TASK:WAC
LANG:PASCAL
}

{$I-,Q-,R-,S-}
uses module;
const
   MAx = 1000000;
var
   BrWord : longint;
   BrEl : longint;
type
   tUser = record
     p,x : longint;
     q : Qword;
   end;
   pel = longint;
   Tel = record
      word : longint;
      next : Pel;
   end;
   TVer = record
      kids : array['a'..'z'] of longint;
      first : PEl;
      last : pel;
   end;
   TQ = object
      Us : array[0..Max] of tuser;
      br : longint;
      procedure Add(var k : tuser);
      procedure get(var k : tuser);
   end;
   TWordTree = Object
      a : array[0..MAx] of TVer;
      wordList : array[1..max] of string[30];
      El : array[1..max] of TEl;
      brA : longint;
      procedure AddWord(var s : string);
      function Find(var s : string) : longint;
   end;
      function TWordTree.Find(var s : string) : longint;
      var
         p,i : longint;
      begin
         p:=0;
         for i:=1 to length(s) do
            begin
               if a[p].kids[s[i]]=0 then
                  begin
                     inc(brA);
                     a[p].kids[s[i]]:=BrA;
                     p:=BrA;
                  end
               else
                  p:=a[p].kids[s[i]];
            end;
         Find:=p;
      end;

      procedure TWordTree.AddWord(var s : string);
      var
         p,i : longint;
      begin
         inc(brWord);
         Wordlist[BrWord]:=s;
         p:=0;
         for i:=1 to length(s) do
            begin
               if a[p].kids[s[i]]=0 then
                  begin
                     inc(brA);
                     a[p].kids[s[i]]:=BrA;
                     p:=BrA;
                  end
               else
                  p:=a[p].kids[s[i]];

               if a[p].first=0 then
                  begin
                     inc(BrEl);
                     a[p].first:=brEl;
                     el[brEl].word:=BrWord;
                     el[BrEl].next:=BrEl;
                     a[p].last:=a[p].first;
                  end
               else
                  begin
                     inc(BrEl);
                     el[brEl].word:=BrWord;
                     el[brEl].next:=el[a[p].last].next;
                     el[a[p].last].next:=brEl;
                     a[p].last:=brEl;
                     el[brEl].word:=BrWord;
                  end;
            end;

      end;
      procedure TQ.Add(var k : tuser);
      var
         i,j,p : longint;
      begin
         if br=0 then
            begin
               inc(br);
               us[1]:=k;
               exit;
            end;
         if k.q>us[br].q then
            begin
               inc(br);
               us[br]:=k;
               exit;
            end;
         if k.q<us[1].q then
            begin
               inc(br);
               for i:=br downto 2 do
                  us[i]:=us[i-1];
               us[1]:=k;
               exit;
            end;
         i:=1;
         j:=br;
         p:=0;
         while i<=j do
            begin
               if us[(i+j) shr 1].q>k.q then
                  begin
                     j:=(i+j) shr 1 -1;
                  end
               else
                  begin
                     if us[(i+j) shr 1].q<k.q then
                        begin
                           i:=(i+j) shr 1 + 1;
                        end
                     else
                        begin
                           p:=(i+j) shr 1;
                           break;
                        end;
                  end;
            end;
         if p=0 then
            begin
               inc(br);
               us[br]:=k;
               i:=br;
               while us[i].q<us[i-1].q do
                  begin
                     k:=us[i-1];
                     us[i-1]:=us[i];
                     us[i]:=k;
                     dec(i);
                  end;
            end
         else
            us[p]:=k;

      end;
      procedure TQ.get(var k : tuser);
      var
         i,j,p : longint;
      begin
         i:=1;
         j:=br;
         p:=0;
         while i<=j do
            begin
               if us[(i+j) shr 1].q>k.q then
                  begin
                     j:=(i+j) shr 1 -1;
                  end
               else
                  begin
                     if us[(i+j) shr 1].q<k.q then
                        begin
                           i:=(i+j) shr 1 + 1;
                        end
                     else
                        begin
                           p:=(i+j) shr 1;
                           break;
                        end;
                  end;
            end;
         k:=us[p];
      end;


var
   s : string;
   t : tWordTree;
   us : TQ;

procedure next(var s : string);
var
   i : longint;
   q : Qword;
   k : TUser;
begin
   q:=0;
   for i:=1 to length(s) do if s[i]<>' '  then
       q:=q shl 4  +byte(s[i]) - 48
   else
      break;
   k.q:=q;
   us.Get(k);

   if k.x=0 then
      begin
        if t.a[k.p].first<>0 then
           begin
              k.x:=t.a[k.p].first;
              s:=t.wordlist[t.el[k.x].word];
              us.Add(k);
           end
        else
           s:='.';


      end

   else
      begin
         k.x:=t.el[k.x].next;
         s:=t.wordlist[t.el[k.x].word];
         us.Add(k);
      end;

end;
procedure First(var s : string);
var
   x,i,p : longint;
   q : Qword;
   k : tuser;
begin
   q:=0;
   for i:=1 to length(s) do if s[i]<>' '  then
       q:=q shl 4  +byte(s[i]) - 48
   else
      break;
   delete(s,1,i);
   p:=t.find(s);
   x:=t.a[p].first;
   if x=0 then  s:='.' else
      s:=t.wordlist[t.el[x].word];
   k.x:=x;
   k.p:=p;
   k.q:=q;
   us.Add(k);
end;

begin
   init;
   while true do
      begin
         getQuery(s);
         case s[1] of
           'F' : begin delete(s,1,6); first(s);AnswerQuery(s); end;
           'N' : begin delete(s,1,5); next(s);AnswerQuery(s); end;
           'A' : begin delete(s,1,4); t.AddWord(s) end;
         end;
      end;

end.
