///SOLUTIE CU BACKTRACKING.
#include <iostream>
using namespace std;
int mat[4][4],v[4][4];
/**Observatie cheie : mutarile se fac modulo 4.
Asadar dupa ce efectuam aceiasi mutare de 4 ori
la rand ne intoarcem in stadiul initial.
Backtrackingul va trece prin toate cele 4^9 mutari = 2^18 = ~260k */

/** ex : 100  va semnifica ca a fost facuta o
         000  singura mutare pe linia 1 col 1.
         000
    Vom folosi baza 4 si vom trece prin toate numerele de la
    000 000 000  la 333 333 333 daca nu exista solutie.
    Altfel vom cauta cea mai scurta solutie, vom pastra  matricea
    si vom afisa mutarile in ordine lexicografica.
*/
int mutare(int linie,int coloana, int val)
{
  for(int i = 1;i<=3;i++)
    for(int j = 1;j<=3;j++)
        if(i==linie||j==coloana)
            v[i][j] = (v[i][j] + val)%4;
}
bool valid()
{
    for(int i = 1;i<=3;i++)
        for(int j = 1;j<=3;j++)
            if(v[i][j]!=0)
                return false;
    return true;
}
int main()
{
    cout<<"Introdu matricea de 3x3 : \n";
    int sol = -1,solsize = -1;
    for(int i = 1;i<=3;i++)
        for(int j = 1;j<=3;j++)
            cin>>mat[i][j];
    for(int comb = 0; comb<(1<<18);comb++)
    {
        int current = comb;
        ///Matricea pe care verificam operatiile este v.
        for(int i = 1;i<=3;i++)
            for(int j = 1;j<=3;j++)
                v[i][j] = mat[i][j];
        ///Trecem prin toate cifrele din baza 4 chiar daca sunt 0.
        //(pentru claritate)
        int nr_mutari = 0;
        for(int i = 1;i <= 3;i++)
        {
            for(int j = 1;j <= 3;j++)
            {
                nr_mutari += (current%4);
                mutare(i,j,current%4);
                current/=4;
                if(valid())
                {
                    if(sol==-1)
                        sol = comb, solsize = nr_mutari;
                    else
                        if(nr_mutari<solsize) sol = comb , solsize = nr_mutari;
                }
            }
        }
    }
    if(sol==-1) cout<<"NU!";
    else
    {
        cout<<"DA\n cea mai scurta solutie contine "<<solsize<<" mutari :\n";
        for(int i = 1;i<=3;i++)
            for(int j = 1;j<=3;j++)
            {
                for(int k = 1;k<=sol%4;k++)
                    cout<<i<<' '<<j<<'\n';
                sol/=4;
            }

    }
    return 0;
}