#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

void citire_sistem(vector<vector<double>>& sistem, int& n, int& m)
{
    int numar;
    vector <double>vectorAux;
    ifstream fin;
    fin.open("input.in");
    fin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            fin >> numar;
            vectorAux.push_back(numar);
        }
        sistem.push_back(vectorAux);
        vectorAux.clear();
    }
    vectorAux.clear();
}

void afisare_sistem(vector<vector<double>>sistem, int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        cout << endl;
        for (int j = 0; j < m; j++)
        {
            cout << sistem[i][j] << " ";
        }
    }
    cout << endl;
}

void determinare_nr_necunoscute_principale(vector<vector<double>>sistem, int n, int& nrNecunoscutePrincipale)
{

    for (int i = 0; i < n; i++)
    {
        if (sistem[i][i] == 1)
        {
            nrNecunoscutePrincipale++;
        }

    }
}

void afisare_solutii(vector<vector<double>>sistem, int n, int m, int tipSistem)
{
    vector<double>vectorDeSolutii;
    if (tipSistem == 1)
    {
        cout << endl << "Solutiile sunt S={";
        for (int i = 0; i < n - 1; i++)
        {
            cout << sistem[i][m - 1] << ", ";
        }
        cout << sistem[n - 1][m - 1] << "}";
    }
    if (tipSistem == 2)
    {
        int nrNecunoscutePrincipale=0;
        determinare_nr_necunoscute_principale(sistem, n, nrNecunoscutePrincipale);
        char indice[8];
        for (int i = 0; i < m - nrNecunoscutePrincipale; i++)
        {
            indice[i] = 'a' + i;
        }
        cout << endl << "Solutiile sunt S={ ";
        for (int i = 0; i < nrNecunoscutePrincipale; i++)
        {
            if (sistem[i][i] == 1)
            {
                cout << sistem[i][m - 1];
                for (int j = nrNecunoscutePrincipale; j < m - 1; j++)
                {
                    if (sistem[i][j] > 0 && sistem[i][j]!=0)
                    {
                        cout<<"-"<< sistem[i][j] << "*" << indice[j - nrNecunoscutePrincipale];
                    }
                    else if(sistem[i][j]!=0)
                    {
                        cout<<"+"<< -1*sistem[i][j] << "*" << indice[j - nrNecunoscutePrincipale];
                    }
                }
            }
            cout << " ; ";
        }
        for (int i = 0; i < m-nrNecunoscutePrincipale-1; i++)
        {
            cout << indice[i] << " ; ";
        }
        cout << "}";
        exit(1);
    }
}


void afisare_tip_sistem(vector<vector<double>>sistem, int n, int m, int& tipSistem)
{
    for (int i = 0; i < n; i++)
    {
        if (sistem[i][i] == 1)
        {
            continue;
        }
        else
        {
            cout << endl << "Sistemul este compatibil nedeterminat" << endl;
            tipSistem = 2;
            return;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m - 1; j++)
        {
            if (i != j && sistem[i][j] != 0)
            {
                cout << endl << "Sistemul este compatibil nedeterminat" << endl;
                tipSistem = 2;
                afisare_solutii(sistem, n, m, tipSistem);
                return;
            }
        }
    }
    cout << endl << "Sistemul este compatibil determinat" << endl;
    tipSistem = 1;
}

void mutare_linie_cu_elemente_nulle(vector<vector<double>>& sistem, int i, int n, int m)
{
    vector<double>vectorAux;
    for (int j = 0; j < m; j++)
    {
        vectorAux.push_back(sistem[i][j]);
    }
    for (int j = i; j < n - 1; j++)
    {
        int counter = 0;
        for (int index = 0; index < m; index++)
        {
            if (sistem[j + 1][index] == 0)
            {
                counter++;
            }
        }
        if (counter != m)
        {
            for (int k = 0; k < m; k++)
            {
                sistem[j][k] = sistem[j + 1][k];
            }
        }
        else
        {
            cout << endl << "Sistemul este compatibil determinat" << endl;
            afisare_solutii(sistem, n - 2, m, 1);
            exit(1);
        }
    }
    cout << endl << "Linia" << i << " a ajuns pe ultima pozitie" << endl;;
    for (int j = 0; j < m; j++)
    {
        sistem[n - 1][j] = vectorAux[j];
    }
    afisare_sistem(sistem, n, m);
}

void interschimbare_linii(vector<vector<double>>& sistem, int linie1, int linie2, int m)
{
    cout << endl << "L" << linie1 << " <-> " << " L" << linie2 << endl;
    for (int j = 0; j < m; j++)
    {
        swap(sistem[linie1][j], sistem[linie2][j]);
    }
}

void verificare_daca_toata_linia_este_zero(vector<vector<double>>& sistem, int& i, int n, int m, bool& interschimbareLinie)
{
    bool esteGasitUnElementNenull = false;
    for (int j = 0; j < m - 1 && esteGasitUnElementNenull == false; j++)
    {
        if (sistem[i][j] != 0)
        {
            esteGasitUnElementNenull = true;
        }
    }
    if (esteGasitUnElementNenull == true)
    {
        if (i + 1 < n)
        {
            interschimbare_linii(sistem, i, i + 1, m);
            afisare_sistem(sistem, n, m);
            interschimbareLinie = true;
        }
    }
    if (interschimbareLinie == false)
    {
        if (sistem[i][m - 1] == 0)
        {
            mutare_linie_cu_elemente_nulle(sistem, i, n, m);
        }
        else
        {
            int counter = 0;
            for (int j = 0; j < m; j++)
            {
                if (sistem[i][j] == 0)
                {
                    counter++;
                }
            }
            if (counter == m - 1)
            {
                cout << "Sistemul este incompatibil";
                exit(1);
            }
        }
    }
}

void verificare_daca_elementul_de_pe_diagonala_principala_este_1(vector<vector<double>>& sistem, int i, int n, int m, bool& interschimbareLinie)
{
    if (sistem[i][i] == 1) return;
    else
    {
        if (sistem[i][i] == 0)
        {
            verificare_daca_toata_linia_este_zero(sistem, i, n, m, interschimbareLinie);
        }
        else
        {
            cout << endl << "L" << i << " <- " << 1 / sistem[i][i] << "L" << i << endl;
            double inmultitorul = 1.0 / sistem[i][i];
            for (int j = 0; j < m; j++)
            {
                if (sistem[i][j] != 0)
                {
                    sistem[i][j] *= inmultitorul;
                }
            }
            afisare_sistem(sistem, n, m);
        }
    }
}

void modificare_elemente_de_sub_diagonala_principala(vector<vector<double>>& sistem, int i, int n, int m)
{
    if (sistem[i][i] == 1)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (sistem[j][i] != 0)
            {
                double inmultitor = sistem[j][i];
                cout << endl << "L" << j << " <- " << "L" << j << " - " << inmultitor << "L" << i << endl;
                for (int k = 0; k < m; k++)
                {
                    sistem[j][k] -= inmultitor * sistem[i][k];
                }
                afisare_sistem(sistem, n, m);
            }
        }
    }
}

void modificare_elemente_de_peste_diagonala_principala(vector<vector<double>>& sistem, int i, int n, int m)
{
    if (sistem[i][i] == 1)
    {
        for (int j = 0; j < i; j++)
        {
            if (sistem[j][i] != 0)
            {
                double inmultitor = sistem[j][i];
                cout << endl << "L" << j << " <- " << "L" << j << " - " << inmultitor << "L" << i << endl;
                for (int k = 0; k < m; k++)
                {
                    sistem[j][k] -= inmultitor * sistem[i][k];
                }
                afisare_sistem(sistem, n, m);
            }
        }
    }
}

void interschimbare_coloane(vector<vector<double>>& sistem, int coloana1, int coloana2, int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        swap(sistem[i][coloana1], sistem[i][coloana2]);
    }
    cout << endl << "Am interschimbat coloana " << coloana1 << " cu coloana " << coloana2 << endl;
    afisare_sistem(sistem, n, m);
}

void verificare_daca_coloanele_se_pot_interschimba(vector<vector<double>>& sistem, int i, int n, int m, bool& interschimbareColoane)
{
    for (int j = i + 1; j < m && interschimbareColoane == false; j++)
    {
        if (sistem[i][j] != 0)
        {
            interschimbare_coloane(sistem, i, j, n, m);
            interschimbareColoane = true;
        }
    }
}

void determinare_solutie_sistem(vector<vector<double>>& sistem, int n, int m)
{
    for (int i = 0; i < n; i++)
    {
        bool interschimbareLinie = false;
        verificare_daca_elementul_de_pe_diagonala_principala_este_1(sistem, i, n, m, interschimbareLinie);
        if (interschimbareLinie == false)
        {
            modificare_elemente_de_sub_diagonala_principala(sistem, i, n, m);
            modificare_elemente_de_peste_diagonala_principala(sistem, i, n, m);
            if (i == n - 1 && sistem[i][i] == 0)
            {
                bool interschimbareColoane = false;
                verificare_daca_coloanele_se_pot_interschimba(sistem, i, n, m, interschimbareColoane);
                if (interschimbareColoane == true)
                {
                    i--;
                }
            }
        }
        else
        {
            i--;
        }
    }
    int tipSistem;
    afisare_tip_sistem(sistem, n, m, tipSistem);
    afisare_solutii(sistem, n, m, tipSistem);
}

int main()
{
    vector<vector<double>>sistem;
    int n, m;
    citire_sistem(sistem, n, m);
    determinare_solutie_sistem(sistem, n, m);
    return 0;
}