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


#include "stdafx.h"
#include <iostream>
#include<vector>
#include<string>

using std::string;
using std::vector;

template <class T>
class HashT
{
public:
	HashT(T Empty, T Delete);
	/*~HashT()
	{
		for (int i = 0; i < size; i++)
			buffer.pop_back();
	}*/
	bool Insert(T& s);
	bool Delete(T& s);
	bool Search(T& s);
private:
	long long size;
	vector<T> buffer;
	long long realsize;
	void grow();
	long long hash1(T& s);
	long long hash2(T& s);
	T DEL;
	T EMP;
};

template<class T>
HashT<T>::HashT(T Empty, T Delete)
{
	EMP = Empty;
	DEL = Delete;
	size = 8;
	realsize = 0;
	buffer.assign(8, EMP);
}

template<class T>
long long HashT<T>::hash1(T& s)
{

	const int a = 17;
	long long h = 0;
	for (int i = 0; i < s.size(); i++) {
		h = (h*a + s[i]) % size;
	}
	return h;
}

template<class T>
long long HashT<T>::hash2(T &s)
{
	long long h= 0;
	int a = 19;
	for (int i = s.size() - 1; i >= 0; i--) {
		h = (h * a + s[i]) % size;
	}

	return h % 2 == 0 ? h + 1 : h;
}

template <class T>
void HashT<T>::grow()
{
	vector<T> oldbuffer = buffer;
	buffer.assign(size * 2, EMP);
	realsize = 0;

	for (int i = 0; i < size; i++) {
		if (oldbuffer[i] != EMP && oldbuffer[i] != DEL) {
			Insert(oldbuffer[i]);
		}
	}
	size *= 2;
}

template <class T>
bool HashT<T>::Insert(T &s)
{
	if (realsize > size * 3 / 4) {
		grow();
	}
	long long place = -1;
	long long h1 = hash1(s);
	long long h2 = hash2(s);
	for (int i = 0; i < size; i++)
	{
		if (buffer[h1] != EMP && buffer[h1] != DEL && buffer[h1] == s)
		{
			return false;
		}
		else
			if (buffer[h1] == EMP) {
				if (place == -1)
					place = h1;
				break;
			}
			else
				if (buffer[h1] == DEL && place == -1)
					place = h1;
		h1 = (h1 + h2) % size;
	}
	if (buffer[place] != EMP) {
		buffer[place] = EMP;
	}
	if (place == -1) {
		return false;
	}
	buffer[place] = s;
	realsize++;
	return true;
}

template <class T>
bool HashT<T>::Delete(T &s)
{
	long long h1 = hash1(s);
	long long h2 = hash2(s);
	for (int i = 0; i < size; i++) {
		if (buffer[h1] != EMP && buffer[h1] != DEL && buffer[h1] == s)
			break;
		else
			if (buffer[h1] == EMP)
				return false;
		h1 = (h1 + h2) % size;
	}
	buffer[h1] = DEL;
	realsize++;
	return true;
}

template <class T>
bool HashT<T>::Search(T &s)
{
	long long h1 = hash1(s);
	long long h2 = hash2(s);
	for (int i = 0; i < size; i++) {
		if (buffer[h1]!=DEL && buffer[h1]!=EMP && buffer[h1] == s)
			return true;
		else
			if (buffer[h1] == DEL)
				break;
		h1 = (h1 + h2) % size;
	}

	return false;
}

int main()
{
	HashT<string>* hashtable = new HashT<string>("EMPTY", "DELETE");
	char operation;
	bool property;
	string s;
	while (std::cin >> operation)
	{
		std::cin >> s;
		operation == '+' ? property = hashtable->Insert(s) : (operation == '-' ? property = hashtable->Delete(s) : property = hashtable->Search(s));
		property ? std::cout << "OK" : std::cout << "FAIL";
		std::cout << std::endl;
	}
	return 0;
	//delete hashtable;
}