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

#include "module.h"

#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstring>
#include <sstream>
#include <iostream>

typedef signed int ind;

const ind buffer_size = 64;

typedef std::string string;
using std::map;
using std::set;

typedef string pnumber;

class word
{
public:
	word() {}
	word(const string& s, const ind& a = 0) : cont(s), aind(a) {}

	string cont;
	ind aind;
};

inline bool is_prefix(const string& pref, const string& str)
{
	if (str.size() < pref.size()) return false;

	for (ind i = 0; i < (ind)pref.size(); i++)
		if (pref[i] != str[i])
			return false;

	return true;
}

inline bool operator< (const word& a, const word& b) {return a.cont < b.cont && !is_prefix(a.cont, b.cont) && !is_prefix(b.cont, a.cont);}

class word_aind_less
{
public:
	inline bool operator() (const word& a, const word& b) {return a.aind < b.aind;}
};

class query
{
public:
	query() {}
	query(const string& p) : prefix(p), last(0) {}

	string prefix;
	ind last;
	std::vector<word> prefix_array;
};

map<pnumber, query> queries;
set<word> words;

std::vector<word> update_prefix_array(const string& pref)
{
	std::pair<set<word>::iterator, set<word>::iterator> p = words.equal_range(word(pref));
	std::vector<word> nu;
	for (set<word>::iterator it = p.first; it != p.second; it++)
		nu.push_back(*it);
	std::sort(nu.begin(), nu.end(), word_aind_less());
	return nu;
}

void add(const string& s)
{
	words.insert(word(s, words.size()));
}

string first(const pnumber& nmb, const string& wrd)
{
	query& q = queries[nmb];
	q = query(wrd);
	q.prefix_array = update_prefix_array(wrd);
	if (q.prefix_array.empty())
	{
		q.prefix_array = update_prefix_array("");
		q.last = -1;
		return ".";
	} else
		return q.prefix_array[0].cont;
}

string next(const pnumber& nmb)
{
	query& q = queries[nmb];
	if (q.last >= (ind)q.prefix_array.size()-1)
	{
		q.prefix_array = update_prefix_array(q.prefix);
		if (q.last >= (ind)q.prefix_array.size()-1) q.last = -1;
	}

	q.last++;

	return q.prefix_array[q.last].cont;
}

int main()
{
	init();

	char buffer [buffer_size];

	while (true)
	{
		getQuery(buffer);
		string buf2(buffer);
		std::istringstream iss(buf2);
		string command, arg1, arg2;
		iss >> command;
		iss >> arg1;
		if (command[0] == 'F') iss >> arg2;

		switch (command[0])
		{
			case 'A': add(arg1); break;
			case 'F': std::strcpy(buffer, first(arg1, arg2).c_str()); answerQuery(buffer); break;
			case 'N': std::strcpy(buffer, next(arg1).c_str()); answerQuery(buffer); break;
		}
	}

	return 0;
}
