#include <bits/stdc++.h>

template<class TKey, class TValue>
class Dictionary
{
public:
    virtual ~Dictionary() = default;

    virtual const TValue& Get(const TKey& key) const = 0;
    virtual void Set(const TKey& key, const TValue& value) = 0;
    virtual bool IsSet(const TKey& key) const = 0;
};

template<class TKey>
class NotFoundException : public std::exception
{
public:
    virtual const TKey& GetKey() const noexcept = 0;
};

template<class TKey>
class ImplNotFoundException : public NotFoundException<TKey> {
private:
    const TKey key;
public:
    explicit ImplNotFoundException(const TKey &key): key(key) {}

    const TKey& GetKey() const noexcept override {
        return key;
    }
};

template <class TKey, class TValue>
class ImplDictionary : public Dictionary<TKey, TValue> {
private:
    std::map<TKey, TValue> dict;
public:
    ImplDictionary() = default;

    ~ImplDictionary() override {
        dict.clear();
    }

    const TValue& Get(const TKey& key) const override{
        if (IsSet(key)) {
            return dict.at(key);
        } else {
            throw(ImplNotFoundException<TKey>(key));
        }
    }

    void Set(const TKey& key, const TValue& value) override {
        dict[key] = value;
    }

    bool IsSet(const TKey& key) const override {
        return dict.find(key) != dict.end();
    }
};

void TrimRight(char *s) {
    char *end = s, *cur = s;

    while (cur++) {
        if (*cur != ' ') {
            if (*cur == 0) {
                break;
            } else {
                end = cur;
            }
        }
    }

    if (*end == ' ' || *end == 0) {
        *end = 0;
    } else {
        *(end + 1) = 0;
    }
}

int main() {
    return 0;
}