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

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>

#include "module.h"

#define DEBUG_ON
#define MAXN		(1<<20)
#define MAXM		(1<<20)
#define MAXLEN		32

struct TrieEntry;

struct HashEntry
{
	char		*cellphone_number;
	char		*prefix;
	int			prog;
	TrieEntry	*curr;
	HashEntry	*next;
};

struct TrieEntry
{
	int			word_num, word_alloced, next_num;
	int			*word_data;
	char		*alpha;
	TrieEntry	**next;
};

int			n;
char		*words[MAXN];
HashEntry	*hashtable[(1<<19)];
TrieEntry	root;

// returns pointer to prog for this cell number
HashEntry* addCellNum(char *cellnumber)
{
	int hashcode, i;
	HashEntry *tmp;

#define HASHNUMBER	((1<<19)-1)

	hashcode = 1;
	i = 0;
	while(cellnumber[i]) { hashcode*=cellnumber[i]; hashcode%=HASHNUMBER; i++;}
	tmp = hashtable[hashcode];

	while(tmp != NULL)
	{
		if(strcmp(tmp->cellphone_number, cellnumber) == 0)
			return tmp;
		tmp = tmp->next;
	}
	tmp = (HashEntry*)malloc(sizeof(HashEntry));

	tmp->prog = 0;
	tmp->cellphone_number = strdup(cellnumber);
	tmp->next = hashtable[hashcode];
	tmp->curr = NULL;
	tmp->prefix = NULL;
	hashtable[hashcode] = tmp;

	return tmp;
}

void addWord(char *word, int index)
{
	int			i, j;
	TrieEntry	*curr;

	curr = &root;
	i = 0;

	while(word[i])
	{
		j = 0;
		while(j<curr->next_num && curr->alpha[j] != word[i] && curr->alpha[j])
			j++;

		if(j == curr->next_num)
		{
			int	 t;
			t = curr->next_num;
			if(!t)	curr->next_num = 1;
			else	curr->next_num *= 2;
			curr->alpha = (char*)realloc(curr->alpha, sizeof(char)*curr->next_num);
			curr->next = (TrieEntry**)realloc(curr->next, sizeof(TrieEntry*)*curr->next_num);
			if(t)		memset(curr->alpha+t*sizeof(char), 0, sizeof(char)*t);
			else		curr->alpha[0] = 0;
		}

		if(!curr->alpha[j])
		{
			curr->alpha[j] = word[i];
			curr->next[j] = (TrieEntry*)malloc(sizeof(TrieEntry));
			curr = curr->next[j];

			curr->alpha = NULL;
			curr->next = NULL;
			curr->next_num = 0;
			curr->word_num = 0;
			curr->word_alloced = 2;
			curr->word_data = (int*)malloc(2*sizeof(int));
		}
		else
			curr=curr->next[j];

		curr->word_data[curr->word_num ++] = index;
		if(curr->word_alloced == curr->word_num)
		{
			int *t;
			t = curr->word_data;
			curr->word_alloced *= 2;
			curr->word_data = (int*)malloc(curr->word_alloced*sizeof(int));
			memcpy(curr->word_data, t, sizeof(int)*curr->word_num);
			free(t);
		}

		i++;
	}
}

TrieEntry* findTrieEntry(char *prefix)
{
	int			i, j;
	TrieEntry	*curr;

	curr = &root;
	i = 0;

	while(prefix[i])
	{
		j = 0;
		while(j<curr->next_num && curr->alpha[j] != prefix[i] && curr->alpha[j])
			j++;

		if(j>=curr->next_num || !curr->alpha[j])
			return NULL;

		curr = curr->next[j];
		i++;
	}

	return curr;
}

int main()
{
	char		tmpstr[64], tmp[MAXLEN], number[MAXLEN], prefix[MAXLEN];
	HashEntry	*curr;

	init();

	while(1)
	{
		getQuery(tmpstr);
		if(tmpstr[0]=='F')	sscanf(tmpstr, "%s %s %s", tmp, number, prefix);
		else				sscanf(tmpstr, "%s %s", tmp, number);

		if(tmp[0]=='A')
		{
			words[n++] = strdup(number);
			addWord(number, n-1);
		}
		else
		{
			curr = addCellNum(number);
			if(tmp[0] == 'F')
			{
				curr->prog = -1;
				if(curr->prefix)
					free(curr->prefix);
				curr->prefix = strdup(prefix);
				curr->curr = NULL;
			}

			if(!curr->curr)
				curr->curr = findTrieEntry(curr->prefix);

			if(!curr->curr)
				answerQuery(".");
			else
			{
				curr->prog ++;
				if(curr->prog >= (curr->curr)->word_num)
					curr->prog = 0;
				answerQuery(words[(curr->curr)->word_data[curr->prog]]);
			}
		}
	}

	return 0;
}
