#include <iostream>
#include <vector>
#include <list>
#include <utility>
#include <iterator>
#include <stdexcept>
#include <algorithm>
#include <string>
#include <typeinfo>
#include <string.h>

template<class ValueType>
void delete_replays(std::vector<ValueType> &ar) {
    if (ar.size() == 0) {
        return;
    }

    int j = 0;
    for (int i = 1; i < ar.size(); ++i) {
        if (ar[i] != ar[j]) {
            ar[++j] = ar[i];
        }
    }
    ar.resize(j + 1);
}

template <class KeyType, class ValueType>
class HashMapIterator {
 private:
    size_t pos;
    typename std::list<std::pair<const KeyType, ValueType>>::iterator it;
    std::vector<std::list<std::pair<const KeyType, ValueType>>> *data;

 public:
    HashMapIterator(): pos(0),
                       data(nullptr) {}

    HashMapIterator(typename std::list<std::pair<const KeyType, ValueType>>::iterator it,
                    std::vector<std::list<std::pair<KeyType, ValueType>>> *data = nullptr,
                    size_t first_pos = 0):
            pos(first_pos),
            it(it),
            data(data) {}

    std::pair<const KeyType, ValueType> &operator*() {
        return *it;
    }

    std::pair<const KeyType, ValueType> *operator->() {
        return &*it;
    }

    HashMapIterator &operator++() {
        ++it;
        if (it != (*data)[pos].end()) {
            return *this;
        }

        ++pos;
        while (pos < data->size() && (*data)[pos].size() == 0) {
            ++pos;
        }

        if (pos < data->size()) {
            it = (*data)[pos].begin();
        } else {
            it = (*data)[data->size() - 1].end();
        }

        return *this;
    }

    HashMapIterator operator++(int) {
        auto res = *this;

        ++*this;

        return res;
    }


    bool operator==(const HashMapIterator &other) const {
        return (pos == other.pos && it == other.it);
    }

    bool operator!=(const HashMapIterator &other) const {
        return !(pos == other.pos && it == other.it);
    }
};

template <class KeyType, class ValueType>
class ConstHashMapIterator {
 private:
    typename std::list<std::pair<const KeyType, ValueType>>::const_iterator it;
    const std::vector<std::list<std::pair<const KeyType, ValueType>>> *data;
    size_t pos;

 public:
    ConstHashMapIterator(): pos(0),
                            data(nullptr) {}

    ConstHashMapIterator(
            typename std::list<std::pair<const KeyType, ValueType>>::const_iterator it,
            const std::vector<std::list<std::pair<const KeyType, ValueType>>> *data = nullptr,
            size_t first_pos = 0):
            it(it),
            data(data),
            pos(first_pos) {}

    const std::pair<const KeyType, ValueType> &operator*() const {
        return *it;
    }

    const std::pair<const KeyType, ValueType> *operator->() const {
        return &*it;
    }

    ConstHashMapIterator &operator++() {
        ++it;
        if (it != (*data)[pos].end()) {
            return *this;
        }

        ++pos;
        while (pos < data->size() && (*data)[pos].size() == 0) {
            ++pos;
        }

        if (pos < data->size()) {
            it = (*data)[pos].begin();
        } else {
            it = (*data)[data->size() - 1].end();
        }

        return *this;
    }

    ConstHashMapIterator operator++(int) {
        auto res = *this;

        ++*this;

        return res;
    }

    bool operator==(const ConstHashMapIterator &other) const {
        return (pos == other.pos && it == other.it);
    }

    bool operator!=(const ConstHashMapIterator &other) const {
        return !(pos == other.pos && it == other.it);
    }
};

template<class KeyType, class ValueType, class Hash = std::hash<KeyType> > class HashMap {
 private:
    size_t data_size = 100000;
    std::vector<std::list<std::pair<const KeyType, ValueType>>> data;
    std::vector<size_t> keys;
    Hash hash;
    size_t cnt, min_key;

 public:
    typedef HashMapIterator<const KeyType, ValueType> iterator;
    typedef ConstHashMapIterator<const KeyType, ValueType> const_iterator;

    // Constructors

    HashMap(Hash hash = Hash()): hash(hash), cnt(0), min_key(data_size) {
        data.resize(data_size);
    }

    template<class TIterator>
    HashMap(TIterator first, TIterator last, Hash hash = Hash()): HashMap(hash) {
        while (first != last) {
            insert(*first++);
        }
    }

    HashMap(std::initializer_list<std::pair<KeyType, ValueType>> items,
            Hash hash = Hash()): HashMap(hash) {
        for (auto item : items) {
            insert(item);
        }
    }

    HashMap &operator=(const HashMap &other) {
        HashMap temp(other);
        temp.swap(*this);
        return *this;
    }

    void swap(HashMap &other) throw() {
        std::swap(cnt, other.cnt);
        std::swap(hash, other.hash);
        std::swap(data_size, other.data_size);
        std::swap(min_key, other.min_key);
        std::swap(keys, other.keys);

        std::vector<std::list<std::pair<const KeyType, ValueType>>> temp;
        temp.resize(data_size);
        for (int i = 0; i < data_size; ++i) {
            for (auto item : data[i]) {
                temp[i].push_back(item);
            }
        }

        data.clear();
        data.resize(data_size);
        for (int i = 0; i < data_size; ++i) {
            for (auto item : other.data[i]) {
                data[i].push_back(item);
            }
        }

        other.data.clear();
        other.data.resize(data_size);
        for (int i = 0; i < data_size; ++i) {
            for (auto item : temp[i]) {
                other.data[i].push_back(item);
            }
        }
    }

    // Iterators

    iterator begin() {
        if (cnt == 0) {
            return end();
        }

        std::sort(keys.begin(), keys.end());
        delete_replays(keys);

        size_t pos = data_size - 1;
        for (auto key : keys) {
            if (!data[key].empty()) {
                pos = key;
                break;
            }
        }

        return iterator(data[pos].begin(), &data, pos);
    }

    iterator end() {
        return iterator(data[data_size - 1].end(), &data, data_size);
    }

    const_iterator begin() const {
        if (cnt == 0) {
            return end();
        }

        size_t pos = data_size - 1;
        for (auto key : keys) {
            if (!data[key].empty()) {
                pos = key;
                break;
            }
        }

        return const_iterator(data[pos].cbegin(), &data, pos);
    }

    const_iterator end() const {
        return const_iterator(data[data_size - 1].cend(), &data, data_size);
    }

    // Realisation

    size_t get_my_hash(const KeyType &key) const {
        return hash(key) % data_size;
    }

    void insert(std::pair<KeyType, ValueType> val) {
        size_t pos = get_my_hash(val.first);

        min_key = std::min(min_key, pos);
        if (data[pos].size() == 0) {
            keys.push_back(pos);
        }

        for (auto it = data[pos].begin(); it != data[pos].end(); ++it) {
            if (it->first == val.first) {
                return;
            }
        }

        ++cnt;
        data[pos].push_back(val);
    }

    void erase(const KeyType &key) {
        size_t pos = get_my_hash(key);

        for (auto it = data[pos].begin(); it != data[pos].end(); ++it) {
            if (it->first == key) {
                --cnt;
                data[pos].erase(it);
                return;
            }
        }
    }

    Hash hash_function() const {
        return hash;
    }

    size_t size() const {
        return cnt;
    }

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

    iterator find(const KeyType &key) {
        size_t pos = get_my_hash(key);

        for (auto it = data[pos].begin(); it != data[pos].end(); ++it) {
            if (it->first == key) {
                return iterator(it, &data, pos);
            }
        }

        return end();
    }

    const_iterator find(const KeyType &key) const {
        size_t pos = get_my_hash(key);

        for (auto it = data[pos].begin(); it != data[pos].end(); ++it) {
            if (it->first == key) {
                return const_iterator(it, &data, pos);
            }
        }

        return end();
    }

    ValueType &operator[](const KeyType &key) {
        size_t pos = get_my_hash(key);
        for (auto it = data[pos].begin(); it != data[pos].end(); ++it) {
            if (it->first == key) {
                return it->second;
            }
        }

        ValueType default_val;

        if (strncmp(typeid(default_val).name(), "i", 1) == 0) {
            insert(std::make_pair(key, static_cast<ValueType>(0)));
        } else {
            insert(std::make_pair(key, default_val));
        }
        return this->operator[](key);
    }

    const ValueType &at(const KeyType &key) const {
        auto res = find(key);
        if (res != end()) {
            return res->second;
        }

        throw std::out_of_range("");
    }

    void clear() {
        cnt = 0;
        min_key = data_size;

        for (auto key : keys) {
            data[key].clear();
        }

        keys.clear();
    }
};