#pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #line 1 "main.cpp" // https://judge.yosupo.jp/submission/70667 #include #include #include #include using namespace std; namespace fastio { struct Pre { char num[10000][4]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i][j] = n % 10 | '0'; n /= 10; } } } } constexpr pre; constexpr int BSZ = 1 << 19; char *ibuf, obuf[BSZ], out[12]; int outi, obufi; void __attribute__((constructor)) _c() { struct stat sb; fstat(0, &sb); ibuf = (char *)mmap(0, sb.st_size, PROT_READ, MAP_SHARED | MAP_POPULATE, 0, 0); } void flush() { write(1, obuf, obufi), obufi = 0; } template void rd(T &x) { char c; for (x = *ibuf++ & 15; (c = *ibuf++) >= '0';) x = x * 10 + (c & 15); } template void wt(T x) { if (obufi > BSZ - 32) flush(); if (x >= 1e16) { long long q0 = x / 100000000; int r0 = x % 100000000; int q1 = q0 / 100000000, r1 = q0 % 100000000; if (x >= 1e18) { memcpy(obuf + obufi, pre.num[q1] + 1, 3); memcpy(obuf + obufi + 3, pre.num[r1 / 10000], 4); memcpy(obuf + obufi + 7, pre.num[r1 % 10000], 4); memcpy(obuf + obufi + 11, pre.num[r0 / 10000], 4); memcpy(obuf + obufi + 15, pre.num[r0 % 10000], 4); obufi += 19; } else if (x >= 1e17) { int q2 = (q1 * 103) >> 10; obuf[obufi] = q2 | '0'; obuf[obufi + 1] = (q1 - q2 * 10) | '0'; memcpy(obuf + obufi + 2, pre.num[r1 / 10000], 4); memcpy(obuf + obufi + 6, pre.num[r1 % 10000], 4); memcpy(obuf + obufi + 10, pre.num[r0 / 10000], 4); memcpy(obuf + obufi + 14, pre.num[r0 % 10000], 4); obufi += 18; } else { obuf[obufi] = q1 | '0'; memcpy(obuf + obufi + 1, pre.num[r1 / 10000], 4); memcpy(obuf + obufi + 5, pre.num[r1 % 10000], 4); memcpy(obuf + obufi + 9, pre.num[r0 / 10000], 4); memcpy(obuf + obufi + 13, pre.num[r0 % 10000], 4); obufi += 17; } } else { for (outi = 8; x >= 10000; outi -= 4) { memcpy(out + outi, pre.num[x % 10000], 4); x /= 10000; } if (x >= 1000) { memcpy(obuf + obufi, pre.num[x], 4); obufi += 4; } else if (x >= 100) { memcpy(obuf + obufi, pre.num[x] + 1, 3); obufi += 3; } else if (x >= 10) { int q = (x * 103) >> 10; obuf[obufi] = q | '0'; obuf[obufi + 1] = (x - q * 10) | '0'; obufi += 2; } else obuf[obufi++] = x | '0'; memcpy(obuf + obufi, out + outi + 4, 8 - outi); obufi += 8 - outi; } obuf[obufi++] = '\n'; } void __attribute__((destructor)) _d() { flush(); } } // namespace fastio using fastio::rd; using fastio::wt; using u32 = unsigned; u32 s[1<<20]; int main() { int h,w; rd(h); rd(w); u32 t = 0; for(int i=0;i