#include <iostream>
#include <vector>

using namespace std;

class PrvokZoznamu {
public:
    int hodnota;
    PrvokZoznamu *dalsi = nullptr;
    PrvokZoznamu *predchadzajuci = nullptr;

    /**
     * @brief Konštruktor pre vytvorenie nového prvku so zadanou hodnotou.
     * @param hodnota Hodnota, ktorú prvok bude obsahovať.
     */
    explicit PrvokZoznamu(int hodnota) : hodnota(hodnota) {
    }

    /**
     * @brief Vytlačí hodnoty všetkých prvkov v zozname, počnúc týmto prvkom.
     */
    void print() {
        cout << hodnota << ", ";
        if (dalsi) {
            dalsi->print();
        }
    }

    /**
     * @brief Vyhľadá prvok so zadanou hodnotou v zozname.
     * @param najdi Hľadaná hodnota.
     * @return Ukazateľ na prvý nájdený prvok alebo nullptr, ak sa nenájde.
     */
    PrvokZoznamu *find(int najdi) {
        if (hodnota == najdi) return this;
        if (dalsi) return dalsi->find(najdi);
        return nullptr;
    }

    /**
     * @brief Získa posledný prvok v zozname.
     * @return Ukazateľ na posledný prvok.
     */
    PrvokZoznamu *last() {
        if (!dalsi) return this;
        else return dalsi->last();
    }

    /**
     * @brief Získa prvý prvok v zozname.
     * @return Ukazateľ na prvý prvok.
     */
    PrvokZoznamu *first() {
        if (!predchadzajuci) return this;
        else return predchadzajuci->first();
    }

    /**
     * @brief Vloží nový prvok so zadanou hodnotou na koniec zoznamu, ak už neexistuje.
     * @param nova_hodnota Hodnota nového prvku.
     * @return Ukazateľ na novo vložený prvok alebo nullptr, ak už existuje.
     */
    PrvokZoznamu *insert(int nova_hodnota) {
        PrvokZoznamu *obsahuje_hodnotu = find(nova_hodnota);
        if (obsahuje_hodnotu) return nullptr;
        PrvokZoznamu *posledny = last();
        PrvokZoznamu *vkladany = new PrvokZoznamu(nova_hodnota);
        posledny->dalsi = vkladany;
        vkladany->predchadzajuci = posledny;
        return vkladany;
    }

    /**
     * @brief Odstráni prvok so zadanou hodnotou zo zoznamu.
     * @param na_vymazanie Hodnota prvku, ktorý sa má odstrániť.
     * @return Ukazateľ na nový začiatok zoznamu po odstránení.
     */
    PrvokZoznamu *remove(int na_vymazanie) {
        if (na_vymazanie == hodnota) {
            if (predchadzajuci) {
                predchadzajuci->dalsi = this->dalsi;
            }
            if (dalsi) {
                dalsi->predchadzajuci = predchadzajuci;
            }
            PrvokZoznamu *prvy = first();
            if (prvy == this) {
                prvy = prvy->dalsi;
                delete this;
            }
            return prvy;
        }
        if (dalsi) dalsi->remove(na_vymazanie);
    }

    /**
     * @brief Vymaže celý zoznam, počnúc posledným prvkom a idúc späť k prvému.
     */
    void clear() {
        PrvokZoznamu *posledny = last();
        while (posledny) {
            if (!posledny->predchadzajuci) {
                delete posledny;
                break;
            }
            posledny = posledny->predchadzajuci;
            delete posledny->dalsi;
        }
    }
};

class HashMap {
public:
    vector<PrvokZoznamu *> buckets;
    int kapacita;

    /**
     * @brief Konštruktor pre vytvorenie hash mapy so zadanou kapacitou.
     * @param kapacita Počet "vedier" hash mapy.
     */
    explicit HashMap(int kapacita) : kapacita(kapacita) {
        for (int i = 0; i < kapacita; i++) {
            buckets.push_back(nullptr);
        }
    }

    /**
     * @brief Vypočíta hash pre danú hodnotu.
     * @param hodnota Hodnota, pre ktorú sa má vypočítať hash.
     * @return Výsledný hash ako index do poľa.
     */
    int calc_hash(int hodnota) const {
        return hodnota % kapacita;
    }

    /**
     * @brief Vytlačí obsah celej hash mapy.
     */
    void print() {
        for (int i = 0; i < buckets.size(); i++) {
            cout << "[" << i << "]" << " : ";
            if (buckets[i]) buckets[i]->print();
            else cout << "NULL";
            cout << endl;
        }
    }

    /**
     * @brief Vloží hodnotu do hash mapy, ak ešte neexistuje.
     * @param hodnota Hodnota, ktorá sa má vložiť.
     * @return true, ak bola hodnota vložená; false, ak už existovala.
     */
    bool insert(int hodnota) {
        const int hash = calc_hash(hodnota);
        if (!buckets[hash]) {
            buckets[hash] = new PrvokZoznamu(hodnota);
            return true;
        } else {
            PrvokZoznamu *zoznam = buckets[hash];
            PrvokZoznamu *vlozeny = zoznam->insert(hodnota);
            return vlozeny != nullptr;
        }
    }

    /**
     * @brief Skontroluje, či daná hodnota existuje v hash mape.
     * @param hodnota Hľadaná hodnota.
     * @return Index vedra, v ktorom sa hodnota nachádza; -1 ak neexistuje.
     */
    int contains(int hodnota) {
        const int hash = calc_hash(hodnota);
        if (!buckets[hash]) return -1;
        PrvokZoznamu *najdeny = buckets[hash]->find(hodnota);
        return najdeny != nullptr ? hash : -1;
    }

    /**
     * @brief Odstráni danú hodnotu z hash mapy.
     * @param hodnota Hodnota, ktorá sa má odstrániť.
     */
    void remove(int hodnota) {
        const int hash = calc_hash(hodnota);
        if (!buckets[hash]) return;
        PrvokZoznamu *novy_prvy = buckets[hash]->remove(hodnota);
        buckets[hash] = novy_prvy;
    }

    /**
     * @brief Dekštruktor, ktorý uvoľní všetky prvky hash mapy.
     */
    ~HashMap() {
        for (PrvokZoznamu *bucket: buckets) {
            bucket->clear();
        }
    }
};