#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
#include <windows.h>
#include <iomanip>

const double PI = 3.141592653589793238462643383279502884197;

using namespace std;

vector<vector<int>> resolve(98);
 int pure=0;

vector<bool> reverse(vector<bool>A)
{
    for(int i=0;i<(int)A.size();i++)
    {
        A[i]=(1-A[i]);
    }
    return A;
}
vector<bool> sum_module(vector<bool> A, vector<bool> B)
{
    vector<bool>C(A.size());

    for(int i=0;i<(int)C.size();i++)
    {
        bool a,b;
        if(A[i]<=(1-B[i]))a=A[i];
        if(B[i]<=(1-A[i]))b=B[i];
        if(a>=b)C[i]=a;
        else C[i]=b;
    }
    return C;
}
int dis_Hemming(vector<bool> A, vector<bool> B)
{
    int sum=0;
    vector<bool>C(A.size());

    for(int i=0;i<(int)C.size();i++)
    {
        bool a,b;
        if(A[i]<=(1-B[i]))a=A[i];
        else a=(1-B[i]);
        if(B[i]<=(1-A[i]))b=B[i];
        else a=(1-A[i]);
        if(a>=b)C[i]=a;
        else C[i]=b;
        sum+=C[i];
    }
    return sum;
}
vector<bool> diff(vector<bool>A,vector<bool>B)
{
    for(int i=0;i<(int)A.size();i++)
    {
        if(A[i]>=(1-B[i]))A[i]=(1-B[i]);
    }
    return A;
}
vector<vector<bool>> transp(vector<vector<bool>> matrix)
{
    vector<vector<bool>> buf;
    buf.resize(matrix[0].size());
    for(int i=0;i<(int)buf.size();i++)
    {
        buf[i].resize(matrix.size());
        for(int j=0;j<(int)buf[i].size();j++)
        {
            buf[i][j]=matrix[j][i];
        }
    }
    return buf;
}
vector<bool> sum(vector<bool> A,vector<bool> B)
{
    for(int i=0;i<(int)A.size();i++)
    {
        if(A[i]<=B[i])A[i]=B[i];
    }
    return A;
}
vector<vector<int>> check(int hl,vector<vector<bool>> A,vector<int>amount)
{
    bool brk=false;
    bool solution=false;
    if(hl>1)
    {
        for(int i=1;i<hl;i++)
        {
            for(int j=0;j<(int)A[i].size();j++)
            {
                //
                if(A[i-1][j]==A[i][j]){cout<<" Для подмножества {";
                                                                    for(int h=0;h<(int)amount.size();h++)
                                                                        cout<<amount[h]<<" ";  cout<<"} нет решений "<<endl; brk=true;break;}
                if(j==A[i].size()-1) A[i]=sum(A[i-1],A[i]);

            }
            if(brk)break;
            if(i==hl-1)
            {
                int sum=0;
                for(int g=0;g<(int)A[i].size();g++)sum+=(int)A[hl-1][g];
                if((float)sum/A[i].size()==1)
                {

                cout<<" Для подмножествa {";
                for(int h=0;h<(int)amount.size();h++)
                    cout<<amount[h]<<" ";
                cout<<"} имеется решение "<<endl;

                solution=true;
                }
                else {cout<<" Для подмножества {";for(int h=0;h<amount.size();h++)
                    cout<<amount[h]<<" ";  cout<<"} нет решений "<<endl;}
            }
        }
    }
    if(hl==1)
    {
                int sum=0;
                for(int g=0;g<(int)A[0].size();g++)sum+=(int)A[hl-1][g];
                if((float)sum/A[0].size()==1)
                {
                cout<<" Для подмножествa {";
                for(int h=0;h<amount.size();h++)
                    cout<<amount[h]<<" ";
                cout<<"} имеется решение "<<endl;
                solution=true;
                }
                else {cout<<" Для подмножества {";for(int h=0;h<(int)amount.size();h++)
                    cout<<amount[h]<<" ";  cout<<"} нет решений "<<endl;}
    }

    if(solution)
    {
        resolve[pure].resize(amount.size());
        for(int d=0;d<(int)resolve[pure].size();d++)
            resolve[pure][d]=amount[d];
        pure++;
    }

    return resolve;
}
int main()
{
    setlocale(0,"");
    ifstream in;
    in.open("matrix.txt");
    vector<vector<bool>> matrix;
    int N,M;


    if (in)
    {
        {
            in>>N;
            in>>M;
            matrix.resize(N);
            for (int i = 0; i < N; i++)
            {
                matrix[i].resize(M);
                for (int j = 0; j < M; j++)
                {
                    bool a;
                    in >> a;
                    matrix[i][j]=a;
                }
            }
        }
        in.close();
    }
            for (int i = 0; i < matrix.size(); i++)
                for (int j = 0; j < matrix[i].size(); j++)
                {
                    cout<<matrix[i][j]<<" ";
                    if(j==matrix[i].size()-1)cout<<endl;
                }
    matrix=transp(matrix);
    cout<<endl;
    for (int i = 0; i < matrix.size(); i++)
                for (int j = 0; j < matrix[i].size(); j++)
                {
                    cout<<matrix[i][j]<<" ";
                    if(j==matrix[i].size()-1)cout<<endl;
                }


    int x, k;
    x= matrix.size();
    k=powf(2,x);
    for (int i=1; i<k; i++)
        {
            vector<vector<bool>> reserv(99);
            vector<int> amount;
            int hl=0;
            for (int j=0; j<x; j++)
            {
                if (i & (1<<j))
                {
                    amount.push_back(j);
                    reserv[hl]= matrix[j] ;
                    hl++;

                }
                 if(j==x-1)check(hl,reserv,amount);
            }
    }


    cout<<"SOLUTION !!!"<<endl;
        for(int i=0;i<pure;i++)
        {
            cout<<" Подмножество {";
            for(int p=0;p<resolve[i].size();p++)
            {
                    cout<<resolve[i][p]<<" ";
            }
            cout<<"} "<<endl;
        }

    system("pause");
    return 0;
}