#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <cstdlib>

using namespace std;

struct ter
{
    int hossz;
    bool teli;
    int kezd;
    int egyesek;
    ter(){};
    ter (int h, bool t, int k, int e)
    {
        hossz=h;
        teli=t;
        kezd=k;
        egyesek=e;
    }
};

struct hasab
{
    vector<int > torzs;
    int trivial;
    int Max;
    int Maxhely;
    int Min;
    int kesz;
    int kesz1;
    int sum;
    int ja0; /// Sor: jobb, Oszlop: alsó
    int bf0; /// Sor: bal, Oszlop: felsõ
    vector<int> versenyben;
    vector<ter> inters;
    int fog; //space with one

    hasab(vector<int> t, int s) //s=size
    {
        kesz=0;
        kesz1=0;
        torzs = t;
        Max=0;
        Maxhely=0;
        trivial=0;
        sum=0;
        fog=0;
        //bf0=0;
        ja0=s-1;
        ter te(s,0,0,0);
        inters.push_back(te);
        for(int i=0; i<t.size(); i++)
        {
            if (torzs[i]>Max) {Max=torzs[i]; Maxhely=i; }

            trivial+=torzs[i]+1;
            sum+=torzs[i];
            versenyben.push_back(2);
        }
        trivial--;

    }
};

struct Rejtveny
{
    bool hiba;
    int osszkesz;
    int sx;
    int sy;
    vector<hasab> elso;
    vector<hasab> masodik;
    vector<vector<int> > mo;
    void Beolvas();
    void Megoldas();
    void Trivialis();
    void Atir(int x, int y, int e);
    void Minusz(char mi, int hol);
    void Mo_maker();
    void Terelo(int x, int y);
    void Keres_0(int x, int y);
    void Advheu_13(int h, char mi);
    void Heuveg(int x, int y, char mi, char irany);
    void Heu_13(int s, char o, int h);
    void Sheu_13(int kezd, int veg, int sz, char o, int s);
};

void Rejtveny::Beolvas()
{
    ifstream f("kod1.txt");
    string s1, s2;
    string kuka;
    hiba=0;
    osszkesz=0;
    getline(f, s1, ';');
    getline(f, s2);
    int s1_int=atoi(s1.c_str());
    int s2_int=atoi(s2.c_str());
    getline(f, kuka);
    sx=s1_int;
    sy=s2_int;

    for (int i=0; i<s1_int; i++)
    {
        vector<int> temp;
        string s;
        stringstream ss;

        getline(f, s);
        ss<<s;

        while(ss.good())
        {
            string s3;
            getline(ss, s3, ',');
            int s3_int=atoi(s3.c_str());
            if (s3_int!=0) temp.push_back(s3_int);
        }
        hasab h (temp,sy);
        h.ja0=sy-1;
        elso.push_back(h);
    }
    getline(f, kuka);
    for (int i=0; i<s2_int; i++)
    {
        vector<int> temp;
        string s;
        stringstream ss;

        getline(f, s);
        ss<<s;

        while(ss.good())
        {
            string s3;
            getline(ss, s3, ',');
            int s3_int=atoi(s3.c_str());
            if (s3_int!=0) temp.push_back(s3_int);
        }
        hasab h (temp,sx);
        h.ja0=sx-1;
        masodik.push_back(h);
    }

//    for(int i=0; i<elso.size(); i++)
//    {
//        for(int j=0; j<elso[i].torzs.size(); j++)
//        {
//            cout << elso[i].torzs[j] << ", ";
//        }
//        cout << endl;
//    }
}

void Rejtveny::Mo_maker()
{
    vector<int> seged1(sy,0);
    vector<vector <int> > seged2(sx,seged1);
    mo=seged2;
}

void Rejtveny::Minusz (char mi, int hol)
{
    if (mi=='s')
    {
        for(int i=0; i<sy; i++)
        {
            if(mo[hol][i]==0) Atir(hol, i, -1);
        }
    }
    if (mi=='o')
    {
        for(int i=0; i<sx; i++)
        {
            if(mo[i][hol]==0) Atir(i, hol, -1);
        }
    }
}

void Rejtveny::Terelo (int x, int y)
{
    ter te;
    te.hossz=0;
    te.egyesek=0;
    vector<ter> elems;
    vector<ter> intert;
    int fog=0;
    elems.push_back(te);
    for (int i=0; i<sy; i++)
    {
        if (mo[x][i]==1) te.egyesek++;
        if (mo[x][i]==-1) {te.hossz=i+1; elems.push_back(te); te.egyesek=0;}
    }
    te.hossz=sy+1;
    elems.push_back(te);
    for (int i=1;i<elems.size();i++)
    {
        te.hossz=elems[i].hossz-elems[i-1].hossz-1;
        te.egyesek=elems[i].egyesek;
        te.kezd=elems[i-1].hossz;
        if (0<te.hossz)
        {
            te.teli=(te.egyesek==te.hossz);
            intert.push_back(te);
            if (te.egyesek > 0) fog++;
        }
    }
    elso[x].inters=intert;
    elso[x].fog=fog;
    te.hossz=0;
    te.egyesek=0;
    elems.clear();
    intert.clear();
    elems.push_back(te);
    for (int i=0; i<sx; i++)
    {
        if (mo[i][y]==1) te.egyesek++;
        if (mo[i][y]==-1) {te.hossz=i+1; elems.push_back(te); te.egyesek=0;}
    }
    te.hossz=sx+1;
    elems.push_back(te);
    fog=0;
    for (int i=1;i<elems.size();i++)
    {
        te.hossz=elems[i].hossz-elems[i-1].hossz-1;
        te.egyesek=elems[i].egyesek;
        te.kezd=elems[i-1].hossz;
        if (0<te.hossz)
        {
            te.teli=(te.egyesek==te.hossz);
            intert.push_back(te);
            if (te.egyesek > 0) fog++;
        }
    }
    masodik[y].inters=intert;
    masodik[y].fog=fog;
}

void potolo(Rejtveny &r, vector<vector<int> > &mo, int x, int y)
{
//    bool jo=0;
//    bool nulla=0;
//     //satírozott)
//    for (int i=y; i>=0; i--)
//    {
//        if (mo[x][i]==1) jo=1;
//        if (mo[x][i]==0) nulla=1;
//        if (mo[x][i]==-1&&i!=y) break;
//    }
//    jo=jo&&nulla;
//
//    if(jo)
//    {
//        for (int i=0; i<r.elso[x].torzs.size(); i++)
//        {
//
//            if()
//        }
//    }
}

void Rejtveny::Keres_0(int x, int y)
{
    if (y==elso[x].ja0)
    {
        for (int i=elso[x].ja0; i>=-1; i--)
        {
            if (i==-1){ elso[x].ja0=-1; break; }
            if (mo[x][i]==0){ elso[x].ja0=i; break; }
        }
    }
    if (y==elso[x].bf0)
    {
        for (int i=elso[x].bf0; i<=sy; i++)
        {
            if (i==sy){ elso[x].bf0=-1; break; }
            if (mo[x][i]==0){ elso[x].bf0=i; break; }
        }
    }
    if (x==masodik[y].ja0)
    {
        for (int i=masodik[y].ja0; i>=-1; i--)
        {
            if (i==-1){ masodik[y].ja0=-1; break; }
            if (mo[i][y]==0){ masodik[y].ja0=i; break; }
        }
    }
    if (x==masodik[y].bf0)
    {
        for (int i=masodik[y].bf0; i<=sx; i++)
        {
            if (i==sx){ masodik[y].bf0=-1; break; }
            if (mo[i][y]==0){ masodik[y].bf0=i; break; }
        }
    }
}

void Rejtveny::Advheu_13(int h, char mi)
{
    vector<hasab> tp;
    int egesz;
    if (mi=='s') { egesz=sy; tp=elso; }
    if (mi=='o') { egesz=sx; tp=masodik; }

    if (tp[h].fog==tp[h].torzs.size())
    {
        int tart=0;
        for (int i=0; i<tp[h].inters.size();i++)
        {
            if (tp[h].inters[i].egyesek==0)
            {
                for (int j=0; j<tp[h].inters[i].hossz; j++)
                {
                    if (mi=='s') Atir(h,tp[h].inters[i].kezd+j,-1);
                    if (mi=='o') Atir(tp[h].inters[i].kezd+j,h,-1);
                }
            }
            else
            {
                tart++;
                int kezd=tp[h].inters[i].kezd;
                if (!tp[h].inters[i].teli)
                {
                    //cout<<kezd<<" "<<kezd+tp[h].inters[i].hossz<<" "<<tp[h].torzs[tart-1]<<" "<<mi<<h<<endl;
                    Sheu_13(kezd,kezd+tp[h].inters[i].hossz,tp[h].torzs[tart-1],mi,h);
                }

            }
        }
    }

}

void Rejtveny::Heuveg(int x, int y, char mi, char irany)
{
    if (mi=='s' && irany=='j')
    {
        int sum=0;
        for (int i=elso[x].ja0; i<sy; i++)
        {
            if (mo[x][i]==1) sum++;
        }
        int sumv=0;
        int j;
        for (int i=elso[x].torzs.size()-1;i>=0;i--)
        {
            sumv+=elso[x].torzs[i];
            if (sumv>=sum)
            {
                j=i;
                break;
            }
        }
        int i;
        for (i=1; i<elso[x].torzs[j]; i++)
        {
            Atir(x,y-i,1);
        }
        if (y-i>=0) Atir(x,y-i,-1);

    }
    if (mi=='s' && irany=='b')
    {
        int sum=0;
        for (int i=elso[x].bf0; i>=0; i--)
        {
            if (mo[x][i]==1) sum++;
        }
        int sumv=0;
        int j;
        for (int i=0;i<=elso[x].torzs.size()-1;i++)
        {
            sumv+=elso[x].torzs[i];
            if (sumv>=sum)
            {
                j=i;
                break;
            }
        }
        int i;
        for (i=1; i<elso[x].torzs[j]; i++)
        {
            Atir(x,y+i,1);
        }
        if (y+i<sy) Atir(x,y+i,-1);
    }
    if (mi=='o' && irany=='j')
    {
        int sum=0;
        for (int i=masodik[y].ja0; i<sx; i++)
        {
            if (mo[i][y]==1) sum++;
        }
        int sumv=0;
        int j;
        for (int i=masodik[y].torzs.size()-1;i>=0;i--)
        {
            sumv+=masodik[y].torzs[i];
            if (sumv>=sum)
            {
                j=i;
                break;
            }
        }
        int i;
        for (i=1; i<masodik[y].torzs[j]; i++)
        {
            Atir(x-i,y,1);
        }
        if (x-i>=0) Atir(x-i,y,-1);
    }
    if (mi=='o' && irany=='b')
    {
        int sum=0;
        for (int i=masodik[y].bf0; i>=0; i--)
        {
            if (mo[i][y]==1) sum++;
        }
        int sumv=0;
        int j;
        for (int i=0;i<=masodik[y].torzs.size()-1;i++)
        {
            sumv+=masodik[y].torzs[i];
            if (sumv>=sum)
            {
                j=i;
                break;
            }
        }
        int i;
        for (i=1; i<masodik[y].torzs[j]; i++)
        {
            Atir(x+i,y,1);
        }
        if (x+i<sx) Atir(x+i,y,-1);

    }
}

void Rejtveny::Atir(int x, int y, int e)
{
    if (mo[x][y]==0)
    {

        mo[x][y]=e;
        elso[x].kesz++;
        masodik[y].kesz++;
        osszkesz++;
        if (e==1)
        {
            if (elso[x].ja0==y) Heuveg(x, y, 's', 'j');
            if (elso[x].bf0==y) Heuveg(x, y, 's', 'b');
            if (masodik[y].ja0==x) Heuveg(x, y, 'o', 'j');
            if (masodik[y].bf0==x) Heuveg(x, y, 'o', 'b');
            elso[x].kesz1++;
            masodik[y].kesz1++;
            if (elso[x].kesz1==elso[x].sum)
            {
                Minusz('s', x);
            }
            if (masodik[y].kesz1==masodik[y].sum)
            {
                Minusz('o', y);
            }
        }
        Terelo(x,y);
        Keres_0(x,y);
    }
    if (mo[x][y]==-e) hiba=1;
}

void Rejtveny::Trivialis()
{
    for (int i=0; i<sx; i++)
    {
        if (elso[i].trivial==sy)
        {
            int f=0;
            for (int j=0; j<elso[i].torzs.size(); j++)
            {
                for (int k=0; k<elso[i].torzs[j]; k++)
                {
                    Atir(i,f, 1);
                    f++;
                }
                if (f<sy) Atir(i,f, -1);
                f++;
            }
        }

        if (elso[i].trivial==0)
        {
            for (int j=0; j<sy; j++)
            {
                Atir(i,j, -1);
            }
        }

    }

    for (int i=0; i<sy; i++)
    {
        if (masodik[i].trivial==sx)
        {
            int f=0;
            for (int j=0; j<masodik[i].torzs.size(); j++)
            {
                for (int k=0; k<masodik[i].torzs[j]; k++)
                {
                    Atir(f,i, 1);
                    f++;
                }
                if (f<sx) Atir(f,i, -1);
                f++;
            }
        }
        if (masodik[i].trivial==0)
        {
            for (int j=0; j<sx; j++)
            {
                Atir(j,i, -1);
            }
        }
    }
}

void Rejtveny::Sheu_13(int kezd, int veg, int sz, char o, int s)
{
    int in=veg-kezd;
    vector<int> sat;
    if (sz>in/2)
    {
        sat.push_back(in-sz);
        sat.push_back(2*sz-in);
        for (int i=0; i<sat[1]; i++)
        {
            if (o=='s') Atir(s,kezd+sat[0]+i,1);
            if (o=='o') Atir(kezd+sat[0]+i,s,1);
        }
    }
}

void Rejtveny::Heu_13 (int s, char o, int h) //s=?sor/oszlop, o=sor/oszlop, h=?elemre
{
    vector<hasab> temp;
    int egesz;
    if (o=='s')
    {
        egesz=sy;
        temp=elso;
    }
    if (o=='o')
    {
        egesz=sx;
        temp=masodik;
    }
    int sum=0;
    int kezd=0;
    vector<int> sat;
    for (int i=0; i<temp[s].torzs.size(); i++)
    {
        if (i>h) sum+=temp[s].torzs[i]+1;
        if (i<h) kezd+=temp[s].torzs[i]+1;
    }
    Sheu_13(kezd,egesz-sum,temp[s].torzs[h],o,s);//temp[s].torzs[temp[s].torzs.size()-1]);
//    if (sat.size()!=0)
//    {
//        for (int i=0; i<sat[1]; i++)
//        {
//            if (o=='s') Atir(s,kezd+sat[0]+i,1);
//            if (o=='o') Atir(kezd+sat[0]+i,s,1);
//        }
//    }
}

void Rejtveny::Megoldas()
{
    Mo_maker();

/// TRIVIALIS
    Trivialis();
    if (hiba)
    {
        cout<<"Hibas!"<<endl;
        return;
    }
    if (osszkesz==sx*sy)
    {
        cout<<"Ez a rejtveny trivialis, tustent megoldhato!"<<endl;
        return;
    }

/// HEU_13 (VALOGATAS)
    for (int i=0; i<elso.size();i++)
    {
        for (int j=0; j<elso[i].torzs.size(); j++)
        {
            int e=elso[i].torzs[j];
            if ((sy-elso[i].trivial+e)<2*e) Heu_13(i, 's', j);

        }
    }
    for (int i=0; i<masodik.size();i++)
    {
        for (int j=0; j<masodik[i].torzs.size(); j++)
        {
            int e=masodik[i].torzs[j];
            if ((sy-masodik[i].trivial+e)<2*e) Heu_13(i, 'o', j);
        }
    }
    for (int j=0;j<2;j++)
    {
        for (int i=0; i<elso.size();i++)
        {
            Advheu_13(i, 's');
        }
        for (int i=0; i<masodik.size();i++)
        {
            Advheu_13(i, 'o');
        }
    }

/// COUT
    cout<<endl;
    /*for (int j=0;j<r.sy;j++){ cout<<endl<<" "<<r.masodik[j].fog<<endl;
    for (int i=0; i<r.masodik[j].inters.size();i++)
    {
        cout<<r.masodik[j].inters[i].hossz<<" "<<r.masodik[j].inters[i].egyesek<<" "<<r.masodik[j].inters[i].kezd<<" "<<r.masodik[j].inters[i].teli<<endl;
    }}*/
    for (int j=0; j<mo.size(); j++)
    {
        for (int i=0; i<mo[j].size(); i++) {if(mo[j][i]>=0) cout<<" "; cout<<mo[j][i]<<" ";}
        cout<<endl;
        //cout<<"      "<<r.elso[j].bf0<<" "<<r.elso[j].ja0<<" "<<endl;
    }
    cout<<endl;
    /*for (int j=0;j<r.sx;j++){ cout<<endl<<" "<<r.elso[j].fog<<endl;
    for (int i=0; i<r.elso[j].inters.size();i++)
    {
        cout<<r.elso[j].inters[i].hossz<<" "<<r.elso[j].inters[i].egyesek<<" "<<r.elso[j].inters[i].kezd<<" "<<r.elso[j].inters[i].teli<<endl;
    }}*/
    //for  (int j=0; j<mo[0].size(); j++) cout<<r.masodik[j].bf0<<" "<<r.masodik[j].ja0<<"     ";
}

int main()
{
    Rejtveny r;
    r.Beolvas();
    r.Megoldas();
    return 0;
}