#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)
#define TARGET_AVX512 \
    __attribute__((target("avx512f,avx512bw,bmi,bmi2,popcnt")))
#else
#define UNLIKELY(x) (x)
#define TARGET_AVX512
#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 void readSpace(
    const char*& p,
    const char* end
) {
    if (UNLIKELY(p == end || *p != ' ')) {
        fail();
    }
    ++p;
}

static 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 <= 1000000000

    数値変換はしない。

    token が
      0～9桁  -> OK
      10桁    -> 先頭 0、または 1000000000
      11桁～  -> NG

    10桁判定も 64 個まとめて bit 演算する。
*/
TARGET_AVX512
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;

    /*
        直前 11 byte 分を保持。

        bit 0..10:
            現在の 64 byte 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;

        if (n == 64) {
            laneMask = ~0ULL;
        } else {
            laneMask = (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
            );
        }

        /*
            digit 判定。

            unsigned(v - '0') < 10
        */
        __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;

        /*
            数字 / ' ' / '\n' / '\r'
            以外は即 NG
        */
        if (UNLIKELY(
            (digit | separators) != laneMask
        )) {
            fail();
        }

        /*
            連続スペースは NG。

            "1  2"
        */
        if (UNLIKELY(space & (space << 1))) {
            fail();
        }

        if (UNLIKELY(
            prevSpace && (space & 1)
        )) {
            fail();
        }

        /*
            ------------------------------
            A <= 1,000,000,000 の SIMD 検査
            ------------------------------
        */

        /*
            直前11 byte + 現在64 byte
            = 75 bit
        */
        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 ten =
            (D << 1)
            & (D << 2)
            & (D << 3)
            & (D << 4)
            & (D << 5)
            & (D << 6)
            & (D << 7)
            & (D << 8)
            & (D << 9)
            & (D << 10);

        /*
            直前11文字も数字なら
            11桁以上なので NG。
        */
        u128 tooLong =
            TERM
            & ten
            & (D << 11);

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

        /*
            ちょうど10桁の token。
        */
        u128 exactly10 =
            TERM
            & ten
            & ~(D << 11);

        if (exactly10 != 0) {
            /*
                token の後ろ9桁が
                すべて '0'
            */
            u128 nineZero =
                (Z << 1)
                & (Z << 2)
                & (Z << 3)
                & (Z << 4)
                & (Z << 5)
                & (Z << 6)
                & (Z << 7)
                & (Z << 8)
                & (Z << 9);

            /*
                10桁で valid なのは

                0xxxxxxxxx
                    または
                1000000000

                先頭 0 なら数値として
                1e9 未満なので OK。
            */
            u128 valid10 =
                (Z << 10)
                |
                (
                    (O << 10)
                    & nineZero
                );

            if (UNLIKELY(
                exactly10 & ~valid10
            )) {
                fail();
            }
        }

        /*
            CR の総数だけ数えておく。

            LF 処理時に CRLF として
            使用された CR の数と比較する。
        */
        crTotal +=
            static_cast<uint64_t>(
                __builtin_popcountll(cr)
            );

        /*
            ------------------------------
            行構造の検査
            ------------------------------

            space 自体は popcount するだけ。
            1個ずつ処理しない。

            LF だけ scalar で処理する。
        */
        uint64_t remainingSpace = space;
        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
                    )
                );

            remainingSpace &= ~lower;

            const char* lineEnd = p + k;

            /*
                この行に W-1 個の空白が
                ちょうど存在する必要がある。
            */
            if (UNLIKELY(
                rowSpaces
                != static_cast<uint64_t>(W - 1)
            )) {
                fail();
            }

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

            const char* dataEnd = lineEnd;

            /*
                CRLF
            */
            if (
                dataEnd > rowBegin &&
                dataEnd[-1] == '\r'
            ) {
                ++crUsed;
                --dataEnd;
            }

            /*
                行の先頭・末尾は数字。
            */
            if (UNLIKELY(
                dataEnd == rowBegin
                || !isDigit(*rowBegin)
                || !isDigit(dataEnd[-1])
            )) {
                fail();
            }

            ++rows;

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

            rowBegin = lineEnd + 1;
            rowSpaces = 0;

            nl &= nl - 1;
        }

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

        /*
            末尾11byteを次 block に渡す。
        */
        if (n == 64) {
            prevDigit =
                (digit >> 53) & 0x7FF;

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

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

            prevSpace =
                ((space >> 63) & 1) != 0;
        } else {
            /*
                最終 block なので
                実際には次回使用されない。
            */
            prevSpace =
                ((space >> (n - 1)) & 1) != 0;
        }

        p += n;
    }

    /*
        行数が H でなければ NG。
    */
    if (UNLIKELY(rows != H)) {
        fail();
    }

    /*
        最終行には必ず EOL が必要。
    */
    if (UNLIKELY(rowBegin != end)) {
        fail();
    }

    /*
        全 CR が CRLF の一部である必要がある。
    */
    if (UNLIKELY(crTotal != crUsed)) {
        fail();
    }
}

int main() {
    struct stat st;

    if (
        fstat(STDIN_FILENO, &st) != 0 ||
        !S_ISREG(st.st_mode)
    ) {
        /*
            pipe fallback
        */
        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;
        }

        const char* p = buf.data();
        const char* end = p + buf.size();

        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
        );

        return 0;
    }

    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) {
        return 1;
    }

    /*
        sequential access のヒント。
    */
    madvise(
        mem,
        size,
        MADV_SEQUENTIAL
    );

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

    const char* end =
        p + size;

    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
    );

    return 0;
}