#include <algorithm>
#include <vector>
#include <iostream>
#include <initializer_list>
#include <iterator>
#include <list>
#include <exception>
#include <string>
#include <ctime>
#include <unordered_map>
#include <utility>

template<class KeyType, class ValueType, class Hash = std::hash<KeyType>>
class HashMap {
public:
    typedef typename std::list<std::pair<const KeyType, ValueType>>::iterator iterator;
    typedef typename std::list<std::pair<const KeyType, ValueType>>::const_iterator const_iterator;

private:
    std::vector<std::vector<iterator>> Data;
    std::list<std::pair<const KeyType, ValueType>> Pairs;
    std::list<size_t> NotEmptyCells;
    Hash hasher;
    std::vector<bool> isEmpty;
    std::vector<std::list<size_t>::iterator> NotEmptyPtr;
public:
    HashMap(Hash hasher_init = Hash()) : hasher(hasher_init),
        isEmpty(std::vector<bool>(765322, true)) {
        Data.resize(765322);
        NotEmptyPtr.resize(765322);
    }

    Hash hash_function() const {
        return hasher;
    }

    HashMap(const std::initializer_list<std::pair<const KeyType, ValueType>>& l,
        Hash hasher_init = Hash()) : hasher(hasher_init),
        isEmpty(std::vector<bool>(765322, true)) {
        Data.resize(765322);
        NotEmptyPtr.resize(765322);
        for (auto el : l) {
            insert(el);
        }
    }

    template <class iterate>
    HashMap(iterate begin, iterate end, Hash hasher_init = Hash()) : hasher(hasher_init),
        isEmpty(std::vector<bool>(765322, true)) {
        Data.resize(765322);
        NotEmptyPtr.resize(765322);
        for (iterate it = begin; it != end; ++it) {
            insert(*it);
        }
    }

    const_iterator begin() const {
        return const_iterator(Pairs.cbegin());
    }

    iterator begin() {
        return iterator(Pairs.begin());
    }

    const_iterator end() const {
        return const_iterator(Pairs.cend());
    }

    iterator end() {
        return iterator(Pairs.end());
    }

    void insert(const std::pair<const KeyType, ValueType>& key) {
        size_t hash = hasher(key.first) % 765322;
        if (find(key.first) == Pairs.end()) {
            Pairs.push_back(key);
            Data[hash].push_back(--Pairs.end());
            if (isEmpty[hash]) {
                NotEmptyCells.push_back(hash);
                isEmpty[hash] = true;
                NotEmptyPtr[hash] = --NotEmptyCells.end();
            }
        }
    }

    void erase(const KeyType& key) {
        size_t hash = hasher(key) % 765322;
        auto it = Data[hash].begin();
        for (it = Data[hash].begin(); it != Data[hash].end(); ++it) {
            if ((*it)->first == key) {
                break;
            }
        }
        if (it != Data[hash].end()) {
            Pairs.erase(*it);
            Data[hash].erase(it);
            if (Data[hash].empty()) {
                isEmpty[hash] = true;
                NotEmptyCells.erase(NotEmptyPtr[hash]);
            }
        }
    }

    size_t size() const {
        return Pairs.size();
    }

    bool empty() const {
        return Pairs.empty();
    }

    void clear() {
        Pairs.clear();
        for (auto empty : NotEmptyCells) {
            Data[empty].clear();
            isEmpty[empty] = true;
        }
    }

    ValueType& operator[](const KeyType& key) {
        if (find(key) != Pairs.end()) {
            size_t hash = hasher(key) % 765322;
            for (auto i : Data[hash]) {
                if (i->first == key) {
                    return i->second;
                }
            }
        }
        else {
            insert(std::make_pair(key, ValueType()));
            return (--Pairs.end())->second;
        }
    }

    const ValueType& at(const KeyType& key) const {
        if (find(key) != Pairs.end()) {
            size_t hash = hasher(key) % 765322;
            for (auto i : Data[hash]) {
                if ((*i).first == key) {
                    return (*i).second;
                }
            }
        }
        else {
            throw std::out_of_range("I HATE PCFS");
        }
    }

    iterator find(const KeyType& key) {
        size_t hash = hasher(key) % 765322;
        for (auto it : Data[hash]) {
            if ((*it).first == key)
                return it;
        }
        return Pairs.end();
    }

    const_iterator find(const KeyType& key) const {
        size_t hash = hasher(key) % 765322;
        for (auto it : Data[hash]) {
            if ((*it).first == key)
                return it;
        }
        return Pairs.cend();
    }
};