#include <cassert>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<size_t> _count_sizes() {
    vector<size_t> res = {32};
    while (res.back() < 4e+6) {
        res.push_back(res.back() * 2);
    }
    return res;
}

vector<size_t> _hash_map_sizes = _count_sizes();

template<class KeyType, class ValueType, class Hash = std::hash<KeyType> >
class HashMap;

namespace impl {

template<class KeyType, class ValueType, class Hash = std::hash<KeyType>, bool Const = false>
class Iterator {
public:
    using reference = typename std::conditional<Const,
            const std::pair<const KeyType, ValueType>&, pair<const KeyType, ValueType>&>::type;
    using table_reference = typename std::conditional<Const,
            const HashMap<KeyType, ValueType, Hash>&, HashMap<KeyType, ValueType, Hash>&>::type;

    using Pair = pair<KeyType, ValueType>;


    Iterator(table_reference t, size_t it):
        it(it),
        t(t)
    {}

    Iterator& operator++() {
        ++it;
        while (it < t.size() && !t._exists(it)) {
            ++it;
        }

        return *this;
    }

    Iterator operator++(int) {
        Iterator t = *this;
        ++*this;
        return t;
    }

    reference operator*() {
        return t.at(it);
    }

    bool operator==(const Iterator& other) const {
        return (&t == &other.t) && (it == other.it);
    }

    bool operator!=(const Iterator& other) const {
        return !(*this == other);
    }
/*
    ValueType operator=(ValueType v) {
        table[
    }
*/ //!!!!!!!!!!!!!
    size_t get_index() const {
        return it;
    }

private:
    size_t it = -1;
    table_reference t;
};

}

template<class KeyType, class ValueType, class Hash = std::hash<KeyType> >
using Iterator = impl::Iterator<KeyType, ValueType, Hash, false>;

template<class KeyType, class ValueType, class Hash = std::hash<KeyType> >
using ConstIterator = impl::Iterator<KeyType, ValueType, Hash, true>;


template<class KeyType, class ValueType, class Hash>
class HashMap {
private:
    using Pair = pair<KeyType, ValueType>;

    size_t n = 0;
    vector<size_t>& sizes = _hash_map_sizes;
    Hash hasher = Hash{};

    vector<Pair> table;
    vector<bool> exists, deleted;

    size_t get_hash(KeyType x) {
        return hasher(x) % table.size();
    }

    void _realloc() {
        HashMap<KeyType, ValueType, Hash> t(begin(), end());
        *this = t;
    }

    void _check() {
        if (table.size() * 7 <= n * 10) {
            _realloc();
        } else if (table.size() > n * 5 && table.size() > sizes[0]) {
            _realloc();
        }
    }

    size_t _find_size(size_t x) {
        return 1;
    }

public:

    HashMap() {
        table.resize(sizes[0]);
        exists.resize(sizes[0]);
        deleted.resize(sizes[0]);
    }

    HashMap(Hash _hasher) {
        hasher = _hasher;
        table.resize(sizes[0]);
        exists.resize(sizes[0]);
        deleted.resize(sizes[0]);
    }

    template<typename Iter>
    HashMap(Iter first, Iter last, Hash _hasher = Hash{}) {
        hasher = _hasher;

        for (auto it = first; it != last; ++it) {
            ++n;
        }
        size_t new_size = _find_size(n);

        table.resize(sizes[new_size]);
        exists.resize(sizes[new_size]);
        deleted.resize(sizes[new_size]);

        for (auto it = first; it != last; ++it) {
            insert(*it, true);
        }
    }

    HashMap(initializer_list<pair<KeyType, ValueType>> lst, Hash _hasher = Hash{}) {
        hasher = _hasher;

        auto first = lst.begin();
        auto last = lst.end();

        n = lst.size();

        size_t new_size = _find_size(n);

        table.resize(sizes[new_size]);
        exists.resize(sizes[new_size]);
        deleted.resize(sizes[new_size]);

        for (auto it = first; it != last; ++it) {
            insert(*it, true);
        }
    }

    int size() const {
        return n;
    }

    bool empty() const {
        return n == 0;
    }

    Hash hash_function() const {
        return hasher;
    }

    void insert(Pair val, bool constructing = false) {
        auto it = find(val);
        if (it != end()) {
            return;
        }

        ++n;

        size_t index = get_hash(val);

        while (exists[index]) {
            ++index;
            index %= table.size();
        }

        table[index] = val;
        exists[index] = true;
        deleted[index] = false;

        if (constructing) {
            return;
        }
        _check();
    }

    void erase(Pair val) {
        auto it = find(val);
        if (it == end()) {
            return;
        }

        --n;

        size_t index = it.get_index();
        deleted[index] = true;
        exists[index] = false;
        table[index] = Pair{};

        _check();
    }

    Iterator<KeyType, ValueType, Hash> begin() {
        return Iterator<KeyType, ValueType, Hash>(*this, 0);
    }

    Iterator<KeyType, ValueType, Hash> end() {
        return Iterator<KeyType, ValueType, Hash>(*this, table.size());
    }

    ConstIterator<KeyType, ValueType, Hash> begin() const {
        return ConstIterator<KeyType, ValueType, Hash>(*this, 0);
    }

    ConstIterator<KeyType, ValueType, Hash> end() const {
        return ConstIterator<KeyType, ValueType, Hash>(*this, table.size());
    }


    Iterator<KeyType, ValueType, Hash> find(Pair val) {
        auto it = get_hash(val.first);
        while (table[it] != val && (exists[it] || deleted[it])) {
            ++it;
            it %= table.size();
        }
        if (table[it] == val) {
            return Iterator<KeyType, ValueType, Hash>(*this, it);
        } else {
            return Iterator<KeyType, ValueType, Hash>(*this, table.size());
        }
    }

    ConstIterator<KeyType, ValueType, Hash> find(Pair val) const {
        auto it = get_hash(val.first);
        while (table[it] != val && (exists[it] || deleted[it])) {
            ++it;
            it %= table.size();
        }
        if (table[it] == val) {
            return ConstIterator<KeyType, ValueType, Hash>(*this, it);
        } else {
            return ConstIterator<KeyType, ValueType, Hash>(*this, table.size());
        }
    }

    Pair& operator[] (KeyType x) {
        auto it = find(x);
        if (it != this->end()) {
            return *it;
        } else {
            insert({x, ValueType{}});
            return *(find(x));
        }
    }

    const Pair& at(KeyType x) {
        auto it = find(x);
        if (it != this->end()) {
            return *it;
        } else {
            throw out_of_range("no key we're so sorry but y'now");
        }
    }

    bool _exists(size_t i) {
        if (i < table.size() && exists[i] && !deleted[i]) {
            return true;
        } else {
            return false;
        }
    }

    void clear() {
        *this = HashMap(hasher);
    }

};