#include <stdio.h>
#include <stdlib.h>

/*
    Algorithme 4 : Prologin 2011

    Nous allons utiliser le pivot de Gauss pour trigonaliser une matrice composée comme expliqué dans les commentaires de la fonction etablitMatrice().
    Ensuite, on cherche une ligne dans la matrice d'équations de forme 0 = 1, ce qui est le seul cas où une grille est insoluble.

    Cette matrice d'équations est de taille (N*M) * (N*(M+1)), ce qui fait une matrice de taille maximale de 2251500 cases, soit 9006000 octets de mémoire en utilisant des integer (soit une grande utilisation de la mémoire).
    Pour cela, nous allons travailler en binaire : nous n'avons besoin de stocker que des 0 et 1. Ainsi, chaque unsigned int permet de stocker 32 valeurs, soit 32 cases du tableau. On aboutit donc à une utilisation de 9006000 / 32 = 281438 octets (diminution massive de la mémoire utilisée).

    Les fonctions getValue() et setValue() servent respectivement à obtenir la valeur d'une case du tableau, et à modifier celle-ci.
    Pour l'allocation dynamique, nous avons besoin d'un nombre multiple de sizeof(unsigned int). Pour cela, la fonction toMultipleOf() arrondit un nombre à une valeur d'un multiple supérieur. La fonction topround(), elle, arrondit un nombre décimal au nombre entier supérieur (le serveur Prologin compilant sans math.h, nous sommes obligés de ré-implémenter la fonction).
*/

int topround(double input) // arrondit à l'unité supérieure (marche sur les nombres posint topround(double input) // arrondit à l'unité supérieure (marche sur les nombres positifs)
{
    int ret=0;

    if(input == (int)input) // si on a affaire à un nommbre déjà arrondi
        ret=input;
    else
        ret=(int)input+1; // on le cast en int (valeur entière en dessous), puis l'incrémente
    return ret;
}

int toMultipleOf(int input, int multiple) // arrondit "input" au multiple de "multiple" supérieur
{
    double division=(double)input / (double)multiple; // division de input par multiple

    if(input/multiple == division) // si input est déjà multiple de multiple
        return input;

    return topround(division) * multiple; // on multiplie l'arrondi supérieur de division par multiple
}

void setValue(unsigned int *binary, char value, int pos)
{
    int caseTableau=pos/32; // une case est un unsigned int, soit 4octets = 32bits. Un sizeof prend du temps à l'exec
    int posInCase=pos%32; // position du bit à modifier dans la case (0 = bit le plus à droite)
    int toAdd=1; // nombre ayant un seul 1 dans son binaire, à l'emplacement de pos

    toAdd = toAdd << posInCase; // on décale le 1

    if((binary[caseTableau] & toAdd) != 0) // si le bit à modif vaut 1
    {
        if(value==1)
            return; // le bit est déjà à la valeur souhaitée
        else
            binary[caseTableau]-=toAdd; // si le bit doit valoir 0, on retire toAdd
    }
    else
    {
        if(value==1)
            binary[caseTableau]+=toAdd;
        else
            return;
    }
}

int getValue(unsigned int *binary, int pos)
{
    // variables : idem setValue()
    int caseTableau=pos/32;
    int posInCase=pos%32;
    int toAdd=1;
    
    toAdd = toAdd << posInCase;

    if((binary[caseTableau] & toAdd) != 0) // si le bit vaut 1
        return 1;

    return 0;
}

void etablitMatrice(int N, int M, int** matrix, unsigned int** systemeEquations)
{
    int y, x, tailleCote = N * M;

    /*
        systemeEquations est une grille représentant les cases affectées par un clic:
        une ligne correspond à une case de matrix: la première case celle de départ,
        les autres cases noircies les cases touchées en même temps que la case de départ.

        On ajoute une dernière colonne représentant l'état de la case dans matrix.
        
        Ce tableau est un système d'équations.
    */


    for(y = 0; y < tailleCote; y++)
    {
        for(x = 0; x < tailleCote; x++)
        {
            if(abs(x%M - y%M) + abs(x/M - y/M) <= 1)
            {
                setValue(systemeEquations[y], 1, x); // noir
            }
            else
            {
                setValue(systemeEquations[y], 0, x); // blanc
            }
        }
    }

    // ===== Remplissage de la dernière colonne =====
    //            ========================

    for(y = 0; y < tailleCote; y++)
    {
        setValue(systemeEquations[y], matrix[y/M][y%M], tailleCote);
    }
}

// efftecue un xor entre les lignes "ligne" et "pivot"
void xorisateur(unsigned int** systemeEquations, int ligne, int pivot, int longueur)
{
    for(int x = 0; x < longueur; x++)
    {
        setValue(systemeEquations[ligne], getValue(systemeEquations[ligne],x) ^ getValue(systemeEquations[pivot],x), x);
    }
}

void estDessinableCorrupted(int N, int M, int** matrix)
{
    // ===== ETAPE 1 ========================
    // initialiser la matrice ("Que la mémoire soit")
    unsigned int **systemeEquations, longueur = N*M; //création de la matrice d'équations
    systemeEquations=calloc(longueur, sizeof(unsigned int*));
    if(systemeEquations == NULL)
    {
        printf("ERROR : allocation bug");
        exit(EXIT_FAILURE);
    }

    for(int y=0; y < longueur; y++)
    {
        // alloue une ligne de minimum longueur+1 bits, où bits est multiple de sizeof(unsigned int)
        systemeEquations[y]=malloc(toMultipleOf(topround((longueur+1)/8), sizeof(unsigned int)));
        if(systemeEquations[y] == NULL)
        {
            printf("ERROR : allocation bug at line %d", y);
            exit(EXIT_FAILURE);
        }
    }
    
    etablitMatrice(N, M, matrix, systemeEquations); //voir commentaires dans etablitMatrice()

    // ===== ETAPE 2 ========================
    // Trigonalisation de la matrice avec le pivot de Gauss.

    for(int fait = 0; fait < longueur; fait++)
    {
        int premierX = -42, premierY = -42; // inutile, donc indispensable.

        //On va parcourir systemeEquations colonne par colonne pour trouver le premier 1
        for(int x=fait; x < longueur && premierX < 0; x++)
        {
            for(int y=fait; y < longueur && premierY < 0; y++)
            {
                if(getValue(systemeEquations[y], x))
                {
                    premierX = x;
                    premierY = y;
                }
            }
        }

        if(premierX == -42) // si aucun 1 n'a été trouvé
        {
            for(int y=fait; y < longueur; y++)
            {
                //et qu'une case de la solution vaut 1 (equation 0=1 impossible)
                if(getValue(systemeEquations[y], longueur))
                {
                    printf("0\n"); //aucune solution n'existe (CAPTAIN OBVIOUS)
                    return;
                }
            }
        }

        if(premierY > fait) //dans le cas où le premier 1 trouvé n'est pas dans la première ligne non faite
            //on applique le xor de manière à pouvoir utiliser la première ligne comme pivot
            xorisateur(systemeEquations, fait, premierY, longueur+1);
        for(int y=fait+1; y<longueur; y++)
        {
            if(getValue(systemeEquations[y], premierX))
                xorisateur(systemeEquations, y, fait, longueur+1); // puis on élimine tous les 1 de la colonne en dessous des lignes faites.
        }
    }

    printf("1\n"); // si on est arrivés jusqu'ici, la solution existe

    // ==== PROLOGUE ===================
    // "Et la mémoire fut libérée".

    for(int i=0; i < N*M; i++)
    {
        free(systemeEquations[i]);
    }
    free(systemeEquations);
}

int main(void)
{
    int N;
    int M;
    int** matrix;

    scanf("%d\n", &N);
    scanf("%d\n", &M);
    matrix = calloc(N, sizeof(int*));
    for(int _l = 0; _l < N; ++_l)
        matrix[_l] = calloc(M, sizeof(int));
    for(int _l = 0; _l < N; ++_l)
        for(int _c = 0; _c < M; ++_c)
            scanf("%d", &matrix[_l][_c]);

    estDessinableCorrupted(N, M, matrix);

    return 0;
}