#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <cstdarg>

using namespace std;

template<unsigned Size, typename T>
class elemlist
{
    class Elem
    {
        typedef set<T> elemlist;
        elemlist elems[Size];
        
        typedef typename elemlist::const_iterator const_iterator;
    public:
        const_iterator begin(unsigned ind) const { return elems[ind].begin(); }
        const_iterator end(unsigned ind) const { return elems[ind].end(); }
        void dump() const
        {
            for(unsigned a=0; a<Size; ++a)
            {
                if(a)cout << '*';
                const_iterator i;
                for(i=begin(a); i!=end(a); ++i)
                    cout << *i;
            }
        }
        bool iscommon(const Elem &b, unsigned ind) const
        {
            return elems[ind] == b.elems[ind];
        }
        unsigned commoncount(const Elem &b) const
        {
            unsigned common = 0;
            for(unsigned a=0; a<Size; ++a)
                if(iscommon(b, a))
                    ++common;
            return common;
        }
        
        void combine(const Elem &b)
        {
            for(unsigned ind=0; ind<Size; ++ind)
                combine(b, ind);
        }
        
        void combine(const Elem &b, unsigned ind)
        {
            const_iterator i;
            for(i=b.begin(ind); i!=b.end(ind); ++i)
                if(elems[ind].find(*i) == end(ind))
                    insert(ind, *i);
        }
        
        bool contains(const Elem &b, unsigned ind) const
        {
            return includes(
                begin(ind), end(ind), 
                b.begin(ind), b.end(ind)
              );
        }
        
        bool contains(const Elem &b) const
        {
            for(unsigned ind=0; ind<Size; ++ind)
                if(!contains(b, ind))return false;
            return true;
        }
        
        const Elem difference(const Elem &b)
        {
            Elem tmp;
            
            for(unsigned a=0; a<Size; ++a)
            {
                //set_difference(begin(a), begin(a),
                //               b.begin(a), b.end(a),
                //               tmp.begin(a));
                
                const_iterator i;
                
                for(i=begin(a); i!=end(a); ++i)
                    if(b.elems[a].find(*i) == b.end(a)) tmp.insert(a, *i);
                
                //for(i=b.begin(a); i!=b.end(a); ++i)
                //    if(elems[a].find(*i) == end(a)) tmp.insert(a, *i);
            }
            return tmp;
        }
        
        void insert(unsigned ind, T elem)
        {
            elems[ind].insert(elem);
        }
        
        void addplot(T coord, ...)
        {
            va_list ap;
            va_start(ap, coord);
            for(unsigned a=0; a<Size; ++a)
            {
                if(a)coord = va_arg(ap, T);
                insert(a, coord);
            }
            va_end(ap);
        }
    };

    vector<Elem> elems;
public:
    void push_back(const Elem &b) { elems.push_back(b); }
    unsigned size() const { return elems.size(); }
    const Elem &operator[] (unsigned n) const { return elems[n]; }
    
    elemlist() { }
    elemlist(Elem &b, unsigned count=1) : elems(count, b) { }
    
    void Replace(unsigned a, const Elem &b)
    {
        elems[a] = b;
    }
    void Erase(unsigned b)
    {
        elems.erase(elems.begin() + b);
    }
    
    void dump() const
    {
        for(unsigned a=0; a<elems.size(); ++a)
        {
            if(a)cout << " + ";
            elems[a].dump();
        }
    }
    
    bool achieves(const elemlist &b) const
    {
        for(unsigned a=0; a<b.elems.size(); ++a)
        {
            for(unsigned c=0; c<elems.size(); ++c)
                if(elems[c].contains(b.elems[a]))goto Ok;
            return false;
        Ok: ;
        }
        return true;
    }

    bool achieves(const elemlist &b, unsigned without) const
    {
        for(unsigned a=0; a<b.elems.size(); ++a)
        {
            for(unsigned c=0; c<elems.size(); ++c)
            {
                if(c == without)continue;
                if(elems[c].contains(b.elems[a]))goto Ok;
            }
            return false;
    Ok: ;
        }
        return true;
    }

    void combine()
    {
    Retry:
        for(unsigned a=0; a<elems.size(); ++a)
        {
            /* Retry-label could be placed here too.
             * It would not cause different results, just group them differently.
             */
            for(unsigned b=a+1; b<elems.size(); ++b)
            {
                unsigned c = elems[a].commoncount(elems[b]);
                if(c == Size - 1)
                {
                    elems[a].combine(elems[b]);
                    elems.erase(elems.begin() + b);
                    goto Retry;
                }
            }
        }
    }
    
    void expand()
    {
        vector<Elem> result;
        
        for(unsigned a=0; a<elems.size(); ++a)
        {
            Elem &e = elems[a];
            Elem::const_iterator ind[Size];
            for(unsigned b=0; b<Size; ++b)
            {
                ind[b] = e.begin(b);
                if(ind[b] == e.end(b))
                    goto Next;
            }
            for(;;)
            {
                Elem tmp;
                for(unsigned c=0; c<Size; ++c)
                    tmp.insert(c, *(ind[c]));
                result.push_back(tmp);
                unsigned b = 0;
            Re:
                if(++ind[b] != e.end(b))continue;
                ind[b] = e.begin(b); if(++b==Size)break;
                goto Re;
            }
        Next: ;
        }
        elems.swap(result);
    }
    
    void join()
    {
        /* Tämä poistaa ylimääräisiä valintoja laittamalla toistensa päälle niitä.
         *
         * Esimerkki:
         *    CE*G  + BCD*HI + E*I
         * -> CE*GI + BCD*HI
         *
         * Menetelmä: E*I:stä kaikki paitsi yksi elementti sisältyy CE*G:hen.
         *            Siispä katsotaan voidaanko *I lisätä CE*G:hen.
         *            Tätä varten muodostetaan lista CE*GI:stä ja katsotaan
         *            mahtuvatko kaikki mainitut elementit alkuperäiseen listaan.
         *
         */
    Retry:
        for(unsigned a=0; a<elems.size(); ++a)
        {
            {elemlist tmp(elems[a]);
            tmp.expand();
            if(achieves(tmp, a))
            {
                cout << "Deleting redundant: "; elems[a].dump(); cout << endl;
                Erase(a);
                goto Retry;
            }}
            for(unsigned c=0; c<elems.size(); ++c)
            {
                if(c!=a)
                {
                    Elem tmp2 = elems[c], tmp = tmp2.difference(elems[a]);
                    tmp2.combine(elems[a]);
                    elemlist comb(tmp2);
                    comb.expand();
                    
                    if(achieves(comb))
                    {
                        cout << "Joining "; elems[c].dump();
                        cout << " to "; elems[a].dump();
                        cout << " as "; tmp2.dump(); cout << endl;
                        Replace(a, tmp2);
                        Erase(c);
                        goto Retry;
                    }
                }
            }
        }
    }
    
    void overlap()
    {
        /* Tämä laajentaa valinnat menemään toistensa päälle. */
        for(unsigned a=0; a<elems.size(); ++a)
            for(unsigned b=a+1; b<elems.size(); ++b)
            {
                bool same[Size]; unsigned samecount = 0;
                for(unsigned c=0; c<Size; ++c)
                {
                    same[c] = elems[b].contains(elems[a], c);
                    if(same[c])++samecount;
                }
                if(samecount == Size-1)
                {
                    unsigned lack=0;
                    cout << "Combining "; elems[a].dump(); cout << " from "; elems[b].dump(); cout << endl;
                    for(unsigned c=0; c<Size; ++c)if(!same[c]){lack=c;break;}
                    elems[a].combine(elems[b], lack);
                }
            }
    }
};

template<unsigned level, typename T>
void BuildDemo(T marked, const T *map, const T *goal, const T *axis, ...)
{
    elemlist<level, T> elems;
    
    unsigned len[level], pos[level];
    const char *axi[level];
    va_list ap;
    va_start(ap, axis);
    for(unsigned a=0; a<level; ++a)
    {
        if(a)axis = va_arg(ap, const T *);
        axi[a] = axis;
        len[a] = strlen(axis);
        pos[a] = 0;
    }
    va_end(ap);
    
    const T *mp = map;
    for(;;)
    {
        if(*mp++ == marked)
        {
            elemlist<level, T>::Elem tmp;
            for(unsigned a=0; a<level; ++a)
                tmp.insert(a, axi[a][pos[a]]);
            elems.push_back(tmp);
        }
        
        unsigned b=0;
    Re:
        if(++pos[b] != len[b])continue;
        pos[b] = 0;
        if(++b == level)break;
        goto Re;
    }
    
    cout << "= "; 
    elems.dump();
    cout << endl;
    
    /* At this point, we have a list of A*B*C -type elements. Singular. */
    
    elems.combine();

    cout << "Combined: ";
    elems.dump();
    cout << endl;
    
    /* Now we have them compiled in arithmetical way.
     * But they can be combined logically too.
     */
    
    elems.overlap();
    cout << "Overlapped: ";
    elems.dump();
    cout << endl;
    
    elems.join();
    cout << "Joined: ";
    elems.dump();
    cout << endl;
    
    elems.overlap();
    cout << "Overlapped: ";
    elems.dump();
    cout << endl;
    
    cout << endl; elems.dump();
            cout << "        = result\n";
    cout << goal << "        = goal\n";
    
    cout << endl << endl;
}

static void BuildDemo()
{
    BuildDemo<2> ('X',
         "..X.X"
         "XXX.X"
         "XXXXX"
         "XXXXX",
         "CE*FGHI + ABCE*GHI + ABCDE*HI",
         "ABCDE", "FGHI");
    
    BuildDemo<2> ('X',
         "....."
         "..X.X"
         ".XXX."
         ".XXXX",
         "CE*GI + BCD*HI",
         "ABCDE", "FGHI");
    
    BuildDemo<2> ('X',
         "X..X."
         "X.X.X"
         "X.XXX"
         "X.XXX",
         "AD*FHI + ACE*GHI",
         "ABCDE", "FGHI");

    BuildDemo<1> ('X',
         "XX.X..X",
         "ABDG",
         "ABCDEFG");

    BuildDemo<3> ('X',
         ".X"
         "XX"
         ".."
         "XX"
         ".."
         "XX",
         
         "B*CD*G + AB*D*GHI",
         
         "AB", "CD", "GHI");
}

int main(void)
{
    BuildDemo();
    
    return 0;
}