/*
Реализуйте структуру данных типа “множество строк” на основе динамической хеш-таблицы с открытой адресацией.
Хранимые строки непустые и состоят из строчных латинских букв.
Хеш-функция строки должна быть реализована с помощью вычисления значения многочлена методом Горнера.
Начальный размер таблицы должен быть равным 8-ми.
Перехеширование выполняйте при добавлении элементов в случае, когда коэффициент заполнения таблицы достигает 3/4.
Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству.
1_1. Для разрешения коллизий используйте квадратичное пробирование. i-ая проба g(k, i)=g(k, i-1) + i (mod m). m - степень двойки.

Идея решения:
Реализована хеш-функция и соответсвующая хеш-таблица. Хеш функция вычисляется методом Горнера.
Причем константа - число, взаимно простое с размером таблицы, который всегда будет степенью двойки.
таким образом хеш-функция может принимать все значения по модулю размера таблицы.
А значит шанс возникновения коллизий уменьшается.

Описан класс Хеш-таблица со след типичными методами:
find. Ищем элемент. Достаточно пройтись до первой свободной ячейки. Мы гарантированно пройдем
все ячейки хеш-функции с помощью квадратичного пробирования(оно нам это и гарантирует).
Поэтому останавливаемся, когда элемент найден или прошли n шагов.
erase. Ищем искомый элемент тем же квадратичным пробированием, и ставим ячейку DELETED.
insert. Вставляем элемент только в пустую ячейку.( До этого квадратичным пробированием проверяя наличие
элемента в таблице.
grow. - Расширение таблицы. Понадобится, когда коэффициент заполнения не станет больше 0,75.
Делается для того, чтобы последующие операции вставки, удаления, поиска проходили за более
короткое время.
(Для себя). Стоит отметить, что квадратичное пробирование не такое уж и эффективное, потому
что для элементов с одинаковыми хеш-функциями последовательность проб будет одна и та же.
(Всего различных последовательностей проб - m из возможных m!)
А вот двойное хеширование немножко смягчает эту проблему: вероятность коллизии при вычислении
двух хешов значителльно уменьшается.( Всего различных последовательностей проб м.б. m^2 из
возможных n!)
А насчет линейного пробирования совсем уж плохо. Образуются огромные кластеры подряд идущих
элементов, поэтому для некоторых элементов за счет увелечения размера кластера вероятность
попадания при следующей пробе достаточно велика.

*/


#include<iostream>
#include<vector>
#include<string>
#include<cmath>

using std::vector;
using std::string;
const int a = 173099;

int Hash_Function(string s, int table_size)
{
	int hash = s[0] % table_size;
	for (auto item = s.begin() + 1; item != s.end(); ++item)
		hash = (hash*a + *item) % table_size;
	return hash;
}

class HashTable {
public:
	HashTable(int size_) : table(size_), size(0) {
		for (int i = 0; i < table.size(); ++i)
			table[i] = " ";
	};
	bool Insert(string s)
	{
		if (4 * size >= table.size() * 3)
			grow();
		int hash = Hash_Function(s, table.size());
		for (int i = 0; i < table.size(); ++i)
		{
			hash = (hash + i) % table.size();
			//std::cout << s << '\t' <<hash << '\n';
			if (table[hash] == " ")
			{
				table[hash] = s;
				break;
			}
			if (table[hash] == s)
				return false;
		}
		++size;
		return true;
	}
	bool erase(string s)
	{
		int n = table.size();
		int hash = Hash_Function(s, table.size());
		for (int i = 0; ; ++i)
		{
			hash = (hash + i) % table.size();
			if (table[hash] == s)
			{
				table[hash] = "DELETED";
				return true;
			}
			if (table[hash] == " ")
				return false;
		}
		return false;
	}
	bool find(string s)
	{
		int n = table.size();
		int hash = Hash_Function(s, table.size());
		for (int i = 0; ; ++i)
		{
			hash = (hash + i) % table.size();
			if (table[hash] == s)
				return true;
			if (table[hash] == " ")
				return false;
		}
	}
private:
	vector<std::string> table;
	int size;
	void grow()
	{
		//std::cout << "grow" << '\n';
		vector<string> New_Table(table.size() * 2);
		for (int i = 0; i < New_Table.size(); ++i) // cannot i use this . Can i use Hash_Table?
			New_Table[i] = " ";
		int size1 = 0;
		for (int i = 0; i < table.size(); ++i)
			if (table[i] != "DELETED" && table[i] != " ")
			{
				int hash = Hash_Function(table[i], New_Table.size());
				for (int j = 0; ; ++j)
				{
					hash = (hash + j) % New_Table.size();
					if (New_Table[hash] == " ")
					{
						++size1;
						New_Table[hash] = table[i];
						break;
					}
				}
			}
		table = New_Table;
		size = size1;
	}
};
int main()
{
	HashTable tb(8);
	string  c;
	while (std::cin >> c)
	{
		string s;
		std::cin >> s;
		if (c == "+")
		{
			if (tb.Insert(s) == 1)
				std::cout << "OK" << '\n';
			else std::cout << "FAIL" << '\n';
			continue;
		}
		if (c == "?")
		{
			if (tb.find(s) == 1)
				std::cout << "OK" << '\n';
			else std::cout << "FAIL" << '\n';
			continue;
		}
		if (tb.erase(s) == 1)
			std::cout << "OK" << '\n';
		else std::cout << "FAIL" << '\n';
	}
}