#include <immintrin.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

#include <cstdint>
#include <cstdlib>
#include <vector>

using u128 = unsigned __int128;

#if defined(__GNUC__)
#define UNLIKELY(x) __builtin_expect(!!(x), 0)
#else
#define UNLIKELY(x) (x)
#endif

[[noreturn]]
static void fail() {
    _exit(1);
}

static inline bool isDigit(char c) {
    return static_cast<unsigned char>(c - '0') <= 9;
}

static uint32_t readUInt(
    const char*& p,
    const char* end,
    uint32_t lo,
    uint32_t hi
) {
    if (UNLIKELY(p == end || !isDigit(*p))) {
        fail();
    }

    uint32_t x = 0;

    do {
        uint32_t d =
            static_cast<uint32_t>(*p - '0');

        if (UNLIKELY(x > (hi - d) / 10)) {
            fail();
        }

        x = x * 10 + d;
        ++p;
    } while (p != end && isDigit(*p));

    if (UNLIKELY(x < lo)) {
        fail();
    }

    return x;
}

static inline void readSpace(
    const char*& p,
    const char* end
) {
    if (UNLIKELY(p == end || *p != ' ')) {
        fail();
    }

    ++p;
}

static inline void readEoln(
    const char*& p,
    const char* end
) {
    if (UNLIKELY(p == end)) {
        fail();
    }

    if (*p == '\n') {
        ++p;
        return;
    }

    if (
        *p == '\r' &&
        p + 1 != end &&
        p[1] == '\n'
    ) {
        p += 2;
        return;
    }

    fail();
}

/*
    A の制約:
        0 <= A <= 1,000,000,000

    各整数を uint32_t に変換するのではなく、
    AVX-512 で 64 byte ずつ文字種を判定する。

    leading zero も許容する。

        000000000000001   -> OK
        0001000000000     -> OK (= 1e9)
        0001000000001     -> NG

    という判定も正しく行う。
*/
__attribute__((
    target("avx512f,avx512bw,bmi,bmi2,popcnt"),
    optimize("O3", "unroll-loops"),
    noinline
))
static void validateBody(
    const char* p,
    const char* end,
    int H,
    int W
) {
    const __m512i C0 =
        _mm512_set1_epi8('0');

    const __m512i C1 =
        _mm512_set1_epi8('1');

    const __m512i C10 =
        _mm512_set1_epi8(10);

    const __m512i CSPACE =
        _mm512_set1_epi8(' ');

    const __m512i CLF =
        _mm512_set1_epi8('\n');

    const __m512i CCR =
        _mm512_set1_epi8('\r');

    const char* rowBegin = p;

    uint64_t rowSpaces = 0;

    uint64_t crTotal = 0;
    uint64_t crUsed = 0;

    int rows = 0;

    /*
        block 境界をまたぐ整数に対応するため、
        直前 11 byte の情報を保持する。
    */
    uint64_t prevDigit = 0;
    uint64_t prevZero = 0;
    uint64_t prevOne = 0;

    bool prevSpace = false;

    while (p < end) {
        size_t rem =
            static_cast<size_t>(end - p);

        unsigned n =
            rem >= 64
                ? 64
                : static_cast<unsigned>(rem);

        uint64_t laneMask =
            n == 64
                ? ~0ULL
                : ((1ULL << n) - 1);

        __m512i v;

        if (n == 64) {
            v = _mm512_loadu_si512(
                reinterpret_cast<const void*>(p)
            );
        } else {
            v = _mm512_maskz_loadu_epi8(
                static_cast<__mmask64>(laneMask),
                p
            );
        }

        /*
            unsigned(c - '0') < 10
            で digit 判定。
        */
        __m512i sub =
            _mm512_sub_epi8(v, C0);

        uint64_t digit =
            static_cast<uint64_t>(
                _mm512_cmp_epu8_mask(
                    sub,
                    C10,
                    _MM_CMPINT_LT
                )
            ) & laneMask;

        uint64_t zero =
            static_cast<uint64_t>(
                _mm512_cmpeq_epi8_mask(v, C0)
            ) & laneMask;

        uint64_t one =
            static_cast<uint64_t>(
                _mm512_cmpeq_epi8_mask(v, C1)
            ) & laneMask;

        uint64_t space =
            static_cast<uint64_t>(
                _mm512_cmpeq_epi8_mask(
                    v,
                    CSPACE
                )
            ) & laneMask;

        uint64_t lf =
            static_cast<uint64_t>(
                _mm512_cmpeq_epi8_mask(
                    v,
                    CLF
                )
            ) & laneMask;

        uint64_t cr =
            static_cast<uint64_t>(
                _mm512_cmpeq_epi8_mask(
                    v,
                    CCR
                )
            ) & laneMask;

        uint64_t separators =
            space | lf | cr;

        /*
            数字 / space / LF / CR
            以外が含まれていたら NG。
        */
        if (UNLIKELY(
            (digit | separators) != laneMask
        )) {
            fail();
        }

        /*
            連続した space は NG。
        */
        if (UNLIKELY(
            space & (space << 1)
        )) {
            fail();
        }

        /*
            block 境界をまたぐ連続 space。
        */
        if (UNLIKELY(
            prevSpace && (space & 1)
        )) {
            fail();
        }

        /*
            直前11文字 + 現在の64文字を
            128-bit mask 上に並べる。

            bit 0..10  : 前 block の末尾11文字
            bit 11..74 : 現在の block
        */
        u128 D =
            (static_cast<u128>(digit) << 11)
            | prevDigit;

        u128 Z =
            (static_cast<u128>(zero) << 11)
            | prevZero;

        u128 O =
            (static_cast<u128>(one) << 11)
            | prevOne;

        u128 TERM =
            static_cast<u128>(separators) << 11;

        /*
            delimiter の直前10文字が
            全部数字かどうか。
        */
        u128 last10digits =
            (D << 1)
            & (D << 2)
            & (D << 3)
            & (D << 4)
            & (D << 5)
            & (D << 6)
            & (D << 7)
            & (D << 8)
            & (D << 9)
            & (D << 10);

        /*
            delimiter の11文字前が non-zero で、
            そこから delimiter まで11桁以上の
            数字が続いていれば、必ず 1e9 超過。

            leading zero はここでは無視されるため、

                000000000000000001

            のような値を誤って reject しない。
        */
        u128 tooLarge11 =
            TERM
            & last10digits
            & (
                static_cast<u128>(D & ~Z)
                << 11
            );

        if (UNLIKELY(tooLarge11 != 0)) {
            fail();
        }

        /*
            delimiter 直前9文字が数字。
        */
        u128 last9digits =
            (D << 1)
            & (D << 2)
            & (D << 3)
            & (D << 4)
            & (D << 5)
            & (D << 6)
            & (D << 7)
            & (D << 8)
            & (D << 9);

        /*
            significant digits が10桁あるケース。

            delimiter の10文字前が non-zero。
        */
        u128 exactly10sig =
            TERM
            & last9digits
            & (
                static_cast<u128>(D & ~Z)
                << 10
            );

        if (UNLIKELY(exactly10sig != 0)) {
            /*
                1e9 以下で10 significant digits
                なのは

                    1000000000

                だけ。
            */
            u128 last9zero =
                (Z << 1)
                & (Z << 2)
                & (Z << 3)
                & (Z << 4)
                & (Z << 5)
                & (Z << 6)
                & (Z << 7)
                & (Z << 8)
                & (Z << 9);

            u128 valid1e9 =
                (O << 10)
                & last9zero;

            if (UNLIKELY(
                exactly10sig & ~valid1e9
            )) {
                fail();
            }
        }

        /*
            CRLF validation 用。
        */
        crTotal +=
            static_cast<uint64_t>(
                __builtin_popcountll(cr)
            );

        /*
            行内の space 数を数える。

            space は1個ずつ処理せず、
            popcount だけで数える。
        */
        uint64_t remainingSpace = space;

        /*
            LF だけは行境界なので処理する。
            最大でも H <= 1,000,000 回。
        */
        uint64_t nl = lf;

        while (nl) {
            unsigned k =
                static_cast<unsigned>(
                    __builtin_ctzll(nl)
                );

            uint64_t lower =
                k == 0
                    ? 0
                    : ((1ULL << k) - 1);

            rowSpaces +=
                static_cast<uint64_t>(
                    __builtin_popcountll(
                        remainingSpace & lower
                    )
                );

            /*
                すでに数えた space を消す。
            */
            remainingSpace &= ~lower;

            const char* lineEnd = p + k;

            /*
                1行に W 個の整数なら、
                space は必ず W-1 個。
            */
            if (UNLIKELY(
                rowSpaces
                != static_cast<uint64_t>(W - 1)
            )) {
                fail();
            }

            /*
                空行禁止。
            */
            if (UNLIKELY(
                rowBegin == lineEnd
            )) {
                fail();
            }

            const char* dataEnd = lineEnd;

            /*
                CRLF の CR を除外。
            */
            if (
                dataEnd > rowBegin &&
                dataEnd[-1] == '\r'
            ) {
                ++crUsed;
                --dataEnd;
            }

            /*
                行頭・行末は数字でなければならない。

                これにより

                    " 1 2"
                    "1 2 "
                    "1 2 \r\n"

                なども reject する。
            */
            if (UNLIKELY(
                dataEnd == rowBegin
                || !isDigit(*rowBegin)
                || !isDigit(dataEnd[-1])
            )) {
                fail();
            }

            ++rows;

            if (UNLIKELY(rows > H)) {
                fail();
            }

            rowBegin = lineEnd + 1;

            rowSpaces = 0;

            nl &= nl - 1;
        }

        /*
            最後の LF より後の space を
            次 block / 次 LF まで持ち越す。
        */
        rowSpaces +=
            static_cast<uint64_t>(
                __builtin_popcountll(
                    remainingSpace
                )
            );

        /*
            次 block のために末尾11文字を保存。
        */
        if (n == 64) {
            prevDigit =
                (digit >> 53) & 0x7FF;

            prevZero =
                (zero >> 53) & 0x7FF;

            prevOne =
                (one >> 53) & 0x7FF;

            prevSpace =
                ((space >> 63) & 1) != 0;
        } else {
            prevSpace =
                ((space >> (n - 1)) & 1) != 0;
        }

        p += n;
    }

    /*
        行数。
    */
    if (UNLIKELY(rows != H)) {
        fail();
    }

    /*
        最終行にも EOL が必要。
        EOL 後に余計な文字があっても NG。
    */
    if (UNLIKELY(rowBegin != end)) {
        fail();
    }

    /*
        CR が存在するなら、すべて
        CRLF の CR でなければならない。
    */
    if (UNLIKELY(crTotal != crUsed)) {
        fail();
    }
}

static void validate(
    const char* begin,
    const char* end
) {
    const char* p = begin;

    int H =
        static_cast<int>(
            readUInt(
                p,
                end,
                1,
                1'000'000
            )
        );

    readSpace(p, end);

    int W =
        static_cast<int>(
            readUInt(
                p,
                end,
                1,
                4'000'000
            )
        );

    if (UNLIKELY(
        static_cast<int64_t>(H) * W
        > 4'000'000
    )) {
        fail();
    }

    readEoln(p, end);

    validateBody(
        p,
        end,
        H,
        W
    );
}

int main() {
    /*
        stdin が通常ファイルなら mmap。
        入力コピーを完全に省略する。
    */
    struct stat st{};

    if (
        fstat(STDIN_FILENO, &st) == 0 &&
        S_ISREG(st.st_mode)
    ) {
        size_t size =
            static_cast<size_t>(st.st_size);

        if (size == 0) {
            return 1;
        }

        void* mem =
            mmap(
                nullptr,
                size,
                PROT_READ,
                MAP_PRIVATE,
                STDIN_FILENO,
                0
            );

        if (mem != MAP_FAILED) {
            madvise(
                mem,
                size,
                MADV_SEQUENTIAL
            );

            const char* begin =
                static_cast<const char*>(mem);

            validate(
                begin,
                begin + size
            );

            return 0;
        }
    }

    /*
        stdin が pipe 等で mmap できない場合。
    */
    std::vector<char> buf;

    buf.reserve(64ULL << 20);

    constexpr size_t CHUNK = 1 << 20;

    char tmp[CHUNK];

    for (;;) {
        ssize_t n =
            read(
                STDIN_FILENO,
                tmp,
                sizeof(tmp)
            );

        if (n < 0) {
            return 1;
        }

        if (n == 0) {
            break;
        }

        buf.insert(
            buf.end(),
            tmp,
            tmp + n
        );
    }

    if (buf.empty()) {
        return 1;
    }

    validate(
        buf.data(),
        buf.data() + buf.size()
    );

    return 0;
}