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

class HashTable
{
    int N = 0; //количество элементов в хеш-таблице
    int M = 8; //размер хеш-таблицы
    double alpha(); //вычисляет коэффициент заполнения хеш-таблицы
    unsigned int h1(std::string&); //первая хеш-функция для строки
    unsigned int h2(std::string&); //вторая хеш-функция для строки
    unsigned int h(std::string&, int); //хеш-функция с номером пробы
    std::vector<std::pair<std::string, bool> > table; //таблицу храним как вектор пар (строка, флаг), где флаг указывает, удалена ли строка.
    void rehash();
    unsigned int string_search(std::string&); //возвращает хеш искомого элемента или М, если элемент не найден. Используется в search и erase.
public:
    HashTable(): table(M) {};
    ~HashTable() = default;
    bool insert(std::string&); //вставка элемента, возвращает true, если она успешна
    bool search(std::string&); //поиск элемента, возвращает true, если элемент найден
    bool erase(std::string&); //удаление элемента, возвращает false, если оно успешно
};

unsigned int HashTable::h1(std::string &s)
{
    int Hash = int(s[0]);
    for(int i = 1; i < s.size(); ++i)
        Hash = Hash * 11719 + int(s[i]);//11719 - простое число.
    return Hash;
}

unsigned int HashTable::h2(std::string &s)
{
    int Hash = int(s[s.size() - 1]);
    for(int i = s.size() - 2; i >= 0; --i)
        Hash = Hash * 11719 + int(s[i]);
    return 2 * Hash + 1; //использовано, чтобы возвращаемое значение было нечетным => взаимно простым с M
}

unsigned int HashTable::h(std::string &s, int i)
{
    return (h1(s) + i * h2(s));
}

double HashTable::alpha()
{
    return double(N) / double(M);
}

void HashTable::rehash()
{
    std::vector<std::pair<std::string, bool> > new_table(2 * M);
    unsigned int Hash;
    for(int i = 0; i < M; ++i)
        if (!table[i].first.empty())
            for(int j = 0; j < 2 * M; ++j)
            {
                Hash = h(table[i].first, j) % (2 * M);
                if (new_table[Hash].first.empty())
                {
                    new_table[Hash].first = table[i].first;
                    new_table[Hash].second = false;
                    break;
                }
            }
    table.resize(2 * M);
    M *= 2;
    table = std::move(new_table); //таблица переносится на нужное место, при этом память не теряется.
}

unsigned int HashTable::string_search(std::string &s)
{
    int m = M;
    unsigned int Hash;
    for(int i = 0; i < M; ++i)
    {
        Hash = h(s, i) % M;
        if (table[Hash].first.empty() && !table[Hash].second)
            break;
        else
            if (!table[Hash].second && s == table[Hash].first)
            {
                m = Hash;
                break;
            }
    }
    return m;
}

bool HashTable::insert(std::string &s)
{
    unsigned int Hash;
    bool f = false;
    for(int i = 0; i < M; ++i)
    {
        Hash = h(s, i) % M;
        if (table[Hash].first.empty())
        {
            f = true;
            table[Hash].first = s;
            table[Hash].second = false;
            N++;
            break;
        }
        else
            if (!table[Hash].second && s == table[Hash].first)
                break;
    }
    if (alpha() >= double(3)/double(4)) rehash();
    return f;
}

bool HashTable::search(std::string &s)
{
    unsigned int Hash = string_search(s);
    if (Hash == M)
        return false;
    return true;
}

bool HashTable::erase(std::string &s)
{
    unsigned int Hash = string_search(s);
    if (Hash == M)
        return false;
    table[Hash].first.clear();
    table[Hash].second = true;
    N--;
    return true;
}

int main()
{
    char c;
    std::string s;
    HashTable h;
    while (std::cin >> c)
    {
        std::cin >> s;
        if (c == '+')
            if (h.insert(s))
                std::cout << "OK\n";
            else
                std::cout << "FAIL\n";
        if (c == '-')
            if (h.erase(s))
                std::cout << "OK\n";
            else
                std::cout << "FAIL\n";
        if (c == '?')
            if (h.search(s))
                std::cout << "OK\n";
            else
                std::cout << "FAIL\n";
    }
    return 0;
}