{
TASK: wac
LANG: PASCAL
}
program wac;

uses
	module;

const
	MAXGSM					= 100000;
	HASHF					= 131071;
	MAXN					= 100000;

type
	Integer					= LongInt;
	TGSM					= record
		i, n				: Integer;
		s, s1				: String;
	end;

var
	q					: String;
	a					: Array [1 .. MAXN] of String;
	g					: Array [1 .. MAXGSM] of TGSM;
	head					: Array [0 .. HASHF-1] of Integer;
	c					: Char;
	i, hash, gn, ind, ian, n		: Integer;
	fnd, fa					: Boolean;
	w, gsm, suff, answ			: String;

procedure print(suff: String; ind: Integer);
var
	i, count				: Integer;
begin
	count := 0;
	for i := 1 to n do
		if (copy(a[i], 1, Length(suff)) = suff) then begin
			count := count + 1;
			if (count = ind) then begin
				answ := a[i];
                                ian := ind + 1;
				Exit;
			end;
		end;
        if (count > 0) then begin
        	ind := 1;
                ian := 2;
		count := 0;
		for i := 1 to n do
			if (copy(a[i], 1, Length(suff)) = suff) then begin
				count := count + 1;
				if (count = ind) then begin
					answ := a[i];
					Exit;
				end;
			end;
        end;
	answ := '.';
end;

begin
	init;
	FillChar(head, sizeof(head), 0);
	n := 0;
	while (True) do begin
		getQuery(q);
		case (q[1]) of
			'A': begin
				w := copy(q, 5, Length(q));
				n := n + 1;
				a[n] := w;
			end;
			'F': begin
				gsm := '';
				i := 7;
				while (q[i] <> ' ') do begin
					gsm := gsm + q[i];
					i := i + 1;
				end;
				suff := copy(q, i+1, Length(q));
				hash := 0;
				for i := 1 to Length(gsm) do
					hash := (hash * ord(gsm[i])) mod HASHF;
				if (head[hash] = 0) then begin
					gn := gn + 1;
					head[hash] := gn;
					g[gn].n := 0;
					g[gn].s := gsm;
					g[gn].s1 := suff;
					g[gn].i := 1;
				end else begin
					i := head[hash];
					fnd := False;
					while (g[i].n > 0) do begin
						if (g[i].s = gsm) then begin
							fnd := True;
							break;
						end;
						i := g[i].n;
					end;
					if (fnd) then begin
						g[i].i := 1;
						g[i].s1 := suff;
					end else begin
						gn := gn + 1;
						g[gn].n := head[hash];
						head[hash] := gn;
						g[gn].s := gsm;
						g[gn].i := 1;
						g[gn].s1 := suff;
						i := gn;
					end;
				end;
				ind := 1;
				print(suff, ind+1);
				answerQuery(answ);
				if (answ = '.') then g[i].i := 1
				else g[i].i := ian;
			end;
			'N': begin
				gsm := copy(q, 6, Length(q));
				hash := 0;
				for i := 1 to Length(gsm) do
					hash := (hash * ord(gsm[i])) mod HASHF;
				i := head[hash];
				while (i > 0) do begin
					if (g[i].s = gsm) then begin
						suff := g[i].s1;
						ind := g[i].i;
						break;
					end;
					i := g[i].n;
				end;
				print(suff, ind);
				answerQuery(answ);
				if (answ = '.') then g[i].i := 1
				else g[i].i := ian;
			end;
		end;
	end;
end.
