#include <iostream>
#include <map>
#include <memory>
#include <utility>

template<typename firstKeyT,
         typename secondKeyT,
         typename mappedT,
         typename CompareT = std::less<std::pair<firstKeyT, secondKeyT> >,
         typename AllocT = std::allocator<std::pair<firstKeyT, secondKeyT> > >
class trimap : public std::map<std::pair<firstKeyT, secondKeyT>,
                               mappedT,
                               CompareT,
                               AllocT>
{
        typedef std::map<std::pair<firstKeyT, secondKeyT>,
                         mappedT,
                         CompareT,
                         AllocT> map_type;

        map_type::insert;

        typedef typename map_type::value_type value_type;
        typedef typename map_type::mapped_type mapped_type;
        typedef typename map_type::iterator iterator;
        typedef typename map_type::const_iterator const_iterator;
        typedef typename map_type::size_type size_type;
        typedef typename map_type::key_compare key_compare;
        typedef typename map_type::value_compare value_compare;
        typedef typename map_type::allocator_type allocator_type;
        typedef typename map_type::reference reference;
        typedef typename map_type::const_reference const_reference;
        typedef typename map_type::difference_type difference_type;
        typedef typename map_type::pointer pointer;
        typedef typename map_type::const_pointer const_pointer;
        typedef typename map_type::reverse_iterator reverse_iterator;
        typedef typename map_type::const_reverse_iterator const_reverse_iterator;

        struct index_proxy1
        {
                trimap& mMap;
                firstKeyT const& mgivenKey;

                index_proxy1(trimap& m,
                            firstKeyT const& k):
                        mMap(m),
                        mgivenKey(k){}

                mapped_type& operator[](secondKeyT const& k)
                {
                        return mMap.map_type::operator[](std::make_pair(mgivenKey, k));
                }
        };

        struct index_proxy2
        {
                trimap& mMap;
                secondKeyT const& mgivenKey;

                index_proxy2(trimap& m,
                            secondKeyT const& k):
                        mMap(m),
                        mgivenKey(k){}

                mapped_type& operator[](firstKeyT const& k)
                {
                        return mMap.map_type::operator[](std::make_pair(k, mgivenKey));
                }
        };

public:

        map_type::end;
        map_type::begin;
        map_type::clear;
        map_type::find;
        map_type::empty;
        map_type::get_allocator;
        map_type::key_comp;
        map_type::max_size;
        map_type::operator=;
        map_type::rbegin;
        map_type::rend;
        map_type::size;
        map_type::swap;
        map_type::value_comp;

        trimap(trimap const& m):
                map_type(m){}

        explicit trimap ( CompareT const& comp = CompareT(),
                          AllocT const& alloc = AllocT() ):
                map_type(comp, alloc) {}

        template <class InputIterator>
                trimap ( InputIterator first,
                      InputIterator last,
                      CompareT& comp = CompareT(),
                      AllocT const& alloc = AllocT() ):
                        map_type(comp, alloc)
                {
                        insert(first, last);
                }


        std::pair<iterator,bool> insert ( const value_type& x )
        {
                typename map_type::iterator t1 = find(x.first),
                                            t2 = find(std::make_pair(x.first.second, x.first.first));
                if(t1 == end()
                && t2 == end())
                        return map_type::insert(x);

                return std::make_pair((t1 == end() ? t2 : t1), false);
        }

        template <class InputIterator>
               void insert ( InputIterator first, InputIterator last )
               {
                       while(first != last)
                        insert(*first++);
               }


        index_proxy1 operator[](firstKeyT const& k)
        {
                return index_proxy1(*this, k);
        }
        index_proxy2 operator[](secondKeyT const& k)
        {
                return index_proxy2(*this, k);
        }

        size_type count(firstKeyT const& k) const
        {
                size_type rval = 0;
                iterator it = begin();
                for(;it != end();++it)
                        if(it->first->first == k)
                                ++rval;

                return rval;
        }
        size_type count(secondKeyT const& k) const
        {
                size_type rval = 0;
                iterator it = begin();
                for(;it != end();++it)
                        if(it->first->second == k)
                                ++rval;

                return rval;
        }

        size_type count(firstKeyT const& k1, secondKeyT const& k2) const
        {
                return map_type::count(std::make_pair(k1, k2));
        }

        std::pair<iterator, iterator> equal_range(firstKeyT const& k)
        {
                return std::make_pair(lower_bound(k), upper_bound(k));
        }

        std::pair<iterator, iterator> equal_range(secondKeyT const& k)
        {
                return std::make_pair(lower_bound(k), upper_bound(k));
        }

        std::pair<const_iterator, const_iterator> equal_range(firstKeyT const& k) const
        {
                return std::make_pair(lower_bound(k), upper_bound(k));
        }

        std::pair<const_iterator, const_iterator> equal_range(secondKeyT const& k) const
        {
                return std::make_pair(lower_bound(k), upper_bound(k));
        }

        iterator lower_bound(firstKeyT const& k)
        {
                iterator rval = begin();
                for(;rval != end();++rval)
                        if(k <= rval->first->first)
                                break;

                return rval;
        }

        const_iterator lower_bound(firstKeyT const& k) const
        {
                const_iterator rval = begin();
                for(;rval != end();++rval)
                        if(k <= rval->first->first)
                                break;

                return rval;
        }

        iterator lower_bound(secondKeyT const& k)
        {
                iterator rval = begin();
                for(;rval != end();++rval)
                        if(k <= rval->first->second)
                                break;

                return rval;
        }

        const_iterator lower_bound(secondKeyT const& k) const
        {
                const_iterator rval = begin();
                for(;rval != end();++rval)
                        if(k <= rval->first->second)
                                break;

                return rval;
        }

        iterator upper_bound(firstKeyT const& k)
        {
                iterator rval = begin();
                for(;rval != end();++rval)
                        if(k < rval->first->first)
                                break;

                return rval;
        }

        const_iterator upper_bound(firstKeyT const& k) const
        {
                const_iterator rval = begin();
                for(;rval != end();++rval)
                        if(k < rval->first->first)
                                break;

                return rval;
        }

        iterator upper_bound(secondKeyT const& k)
        {
                iterator rval = begin();
                for(;rval != end();++rval)
                        if(k < rval->first->second)
                                break;

                return rval;
        }

        const_iterator upper_bound(secondKeyT const& k) const
        {
                const_iterator rval = begin();
                for(;rval != end();++rval)
                        if(k < rval->first->second)
                                break;

                return rval;
        }

        void erase ( iterator position ){map_type::erase(position);}
        void erase ( iterator first, iterator last ){map_type::erase(first, last);}

        size_type erase ( const firstKeyT& x )
        {
                size_type rval = 0;
                for(iterator it = begin();it != end();++it)
                        if(it->first->first == x)
                        {
                                iterator toerase = it++;
                                erase(toerase);
                                ++rval;
                        }
                return rval;
        }
        size_type erase ( const secondKeyT& x )
        {
                size_type rval = 0;
                for(iterator it = begin();it != end();++it)
                        if(it->first->second == x)
                        {
                                iterator toerase = it++;
                                erase(toerase);
                                ++rval;
                        }
                return rval;
        }

        iterator find(firstKeyT const& k)
        {
                iterator rval = begin();
                for(;rval != end();++rval)
                        if(rval->first->first == k)
                                break;

                return rval;
        }

        const_iterator find(firstKeyT const& k) const
        {
                const_iterator rval = begin();
                for(;rval != end();++rval)
                        if(rval->first->first == k)
                                break;

                return rval;
        }

        iterator find(secondKeyT const& k)
        {
                iterator rval = begin();
                for(;rval != end();++rval)
                        if(rval->first->first == k)
                                break;

                return rval;
        }

        const_iterator find(secondKeyT const& k) const
        {
                const_iterator rval = begin();
                for(;rval != end();++rval)
                        if(rval->first->second == k)
                                break;

                return rval;
        }
};

template<typename KeyTs,
         typename mappedT,
         typename CompareT,
         typename AllocT>
class trimap<KeyTs,
             KeyTs,
             mappedT,
             CompareT,
             AllocT> : public std::map<std::pair<KeyTs, KeyTs>,
                                       mappedT,
                                       CompareT,
                                       AllocT>
{
        typedef std::map<std::pair<KeyTs, KeyTs>,
                         mappedT,
                         CompareT,
                         AllocT> map_type;

        map_type::insert;

        typedef typename map_type::value_type value_type;
        typedef typename map_type::mapped_type mapped_type;
        typedef typename map_type::iterator iterator;
        typedef typename map_type::const_iterator const_iterator;
        typedef typename map_type::size_type size_type;
        typedef typename map_type::key_compare key_compare;
        typedef typename map_type::value_compare value_compare;
        typedef typename map_type::allocator_type allocator_type;
        typedef typename map_type::reference reference;
        typedef typename map_type::const_reference const_reference;
        typedef typename map_type::difference_type difference_type;
        typedef typename map_type::pointer pointer;
        typedef typename map_type::const_pointer const_pointer;
        typedef typename map_type::reverse_iterator reverse_iterator;
        typedef typename map_type::const_reverse_iterator const_reverse_iterator;

        struct index_proxy
        {
                trimap& mMap;
                KeyTs const& mgivenKey;

                index_proxy(trimap& m,
                            KeyTs const& k):
                        mMap(m),
                        mgivenKey(k){}

                mapped_type& operator[](KeyTs const& k)
                {
                        const_iterator end_i = mMap.end();
                        iterator iter  = mMap.find(std::make_pair(mgivenKey, k)),
                                 iter2 = mMap.find(std::make_pair(k, mgivenKey));

                        if(iter != end_i)
                                return iter->second;
                        else if(iter2 != end_i)
                                return iter2->second;
                        else
                                return mMap.map_type::operator[](std::make_pair(mgivenKey, k));
                }
        };

public:

        map_type::end;
        map_type::begin;
        map_type::clear;
        map_type::find;
        map_type::empty;
        map_type::get_allocator;
        map_type::key_comp;
        map_type::max_size;
        map_type::operator=;
        map_type::rbegin;
        map_type::rend;
        map_type::size;
        map_type::swap;
        map_type::value_comp;

        trimap(trimap const& m):
                map_type(m){}

        explicit trimap ( CompareT const& comp = CompareT(),
                          AllocT const& alloc = AllocT() ):
                map_type(comp, alloc) {}

        template <class InputIterator>
                trimap ( InputIterator first,
                      InputIterator last,
                      CompareT& comp = CompareT(),
                      AllocT const& alloc = AllocT() ):
                        map_type(comp, alloc)
                {
                        insert(first, last);
                }

        std::pair<iterator,bool> insert ( const value_type& x )
        {
                typename map_type::iterator t1 = find(x),
                                            t2 = find(std::make_pair(x.second, x.first));
                if(t1 == end()
                && t2 == end())
                        return map_type::insert(x);

                return std::make_pair((t1 == end() ? t2 : t1), false);
        }

        template <class InputIterator>
               void insert ( InputIterator first, InputIterator last )
               {
                       while(first != last)
                        insert(*first++);
               }

        index_proxy operator[](KeyTs const& k)
        {
                return index_proxy(*this, k);
        }

        size_type count(KeyTs const& k) const
        {
                size_type rval = 0;
                iterator it = begin();
                for(;it != end();++it)
                {
                        bool const second_eq = it->first->second == k,
                                   first_eq = it->first->first == k;

                        if(first_eq and second_eq)
                                rval += 2;

                        else if(first_eq or second_eq)
                                ++rval;
                }

                return rval;
        }

        size_type count(KeyTs const& k1, KeyTs const& k2) const
        {
                return map_type::count(std::make_pair(k1, k2)) + map_type::count(std::make_pair(k2, k1));
        }

        void erase ( iterator first, iterator last ){map_type::erase(first, last);}
        void erase ( iterator position ){map_type::erase(position);}

        size_type erase ( const KeyTs& x )
        {
                size_type rval = 0;
                for(iterator it = begin();it != end();++it)
                        if(it->first->first == x
                        or it->first->second == x)
                        {
                                iterator toerase = it++;
                                erase(toerase);
                                ++rval;
                        }
                return rval;
        }

        iterator find(KeyTs const& k)
        {
                iterator rval = begin();
                for(;rval != end();++rval)
                        if(rval->first->first == k
                        or rval->first->second == k)
                                break;

                return rval;
        }

        const_iterator find(KeyTs const& k) const
        {
                const_iterator rval = begin();
                for(;rval != end();++rval)
                        if(rval->first->first == k
                        or rval->first->second == k)
                                break;

                return rval;
        }
};


int main()
{

}