#define SINGLE_TESTCASE // #define MULTI_TESTCASE // #define AOJ_TESTCASE // #define FAST_IO // #define FAST_CIO #define INTERACTIVE #define INF 4'000'000'000'000'000'037LL #define EPS 1e-11 // https://github.com/miscalculation53/library/tree/wip/template/template_all.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_all_but_modint.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_types.hpp #include namespace { using namespace std; using ld = decltype(EPS); using ll = long long; using uint = unsigned int; using ull = unsigned long long; using pll = pair; #define vc vector template using vvc = vc>; using vstr = vc; using i128 = __int128_t; using u128 = __uint128_t; i128 stoi128(const string &s) { const bool neg = s.front() == '-'; u128 res = 0; for (int i = neg; i < (int)s.size(); i++) res = 10 * res + s[i] - '0'; if (neg) return -i128(res - 1) - 1; return i128(res); } string i128tos(i128 x) { if (x == 0) return "0"; string sign = "", res = ""; u128 ux; if (x < 0) ux = u128(-(x + 1)) + 1, sign = "-"; else ux = x; while (ux > 0) { res += '0' + ux % 10; ux /= 10; } reverse(res.begin(), res.end()); return sign + res; } istream &operator>>(istream &is, i128 &a) { string s; is >> s; a = stoi128(s); return is; } ostream &operator<<(ostream &os, const i128 &a) { os << i128tos(a); return os; } #define cauto const auto // https://github.com/miscalculation53/library/tree/wip/template/template_rep.hpp #define overload4(_1,_2,_3,_4,name,...) name #define rep1(i,n) for (ll i = 0, nnnnn = ll(n); i < nnnnn; i++) #define rep2(i,l,r) for (ll i = ll(l), rrrrr = ll(r); i < rrrrr; i++) #define rep3(i,l,r,d) for (ll i = ll(l), rrrrr = ll(r), ddddd = ll(d); ddddd > 0 ? i < rrrrr : i > rrrrr; i += d) #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi1(i,n) for (int i = 0, nnnnn = int(n); i < nnnnn; i++) #define repi2(i,l,r) for (int i = int(l), rrrrr = int(r); i < rrrrr; i++) #define repi3(i,l,r,d) for (int i = int(l), rrrrr = int(r), ddddd = int(d); ddddd > 0 ? i < rrrrr : i > rrrrr; i += d) #define repi(...) overload4(__VA_ARGS__, repi3, repi2, repi1)(__VA_ARGS__) #define fe(...) for (auto __VA_ARGS__) #define fec(...) for (cauto &__VA_ARGS__) #define fem(...) for (auto &__VA_ARGS__) // https://github.com/miscalculation53/library/tree/wip/template/template_math.hpp // https://github.com/miscalculation53/library/tree/wip/utils/is_integral_ext.hpp template constexpr bool is_integral_ext = is_integral_v || is_same_v || is_same_v; template constexpr bool is_signed_ext = is_signed_v || is_same_v; template constexpr bool is_unsigned_ext = is_unsigned_v || is_same_v; // https://github.com/miscalculation53/library/tree/wip/utils/default_infty.hpp namespace default_infty_detail { template struct has_infty : false_type {}; template struct has_infty> : true_type {}; template inline constexpr bool unsupported = false; } template && is_integral_ext>> inline constexpr T divfloor(U a, V b) { return T(a) / T(b) - (T(a) % T(b) && (T(a) ^ T(b)) < 0); } template && is_integral_ext>> inline constexpr T safemod(U a, V b) { return T(a) - T(b) * divfloor(a, b); } // https://github.com/miscalculation53/library/tree/wip/template/template_vector.hpp #define ALL(a) (a).begin(), (a).end() template inline T SZ(const V &x) { return x.size(); } #define eb emplace_back #define LMD(x,fx) ([&](const auto &x) { return fx; }) #define GEN_VEC(n,i,fi) (gen_vec(n, LMD(i, fi))) // https://github.com/miscalculation53/library/tree/wip/template/template_algo.hpp // https://github.com/miscalculation53/library/tree/wip/utils/resolved_infty.hpp // https://github.com/miscalculation53/library/tree/wip/utils/resolved_value.hpp template vvc top(const vvc &a) { if (a.empty()) return {}; const int n = a.size(), m = a[0].size(); vvc b(m, vc(n)); repi(i, n) { assert(SZ(a[i]) == m); repi(j, m) b[j][i] = a[i][j]; } return b; } vstr top(const vstr &a) { vvc a_(a.size()); repi(i, SZ(a)) a_[i] = {ALL(a[i])}; vvc b_ = top(a_); vstr b(b_.size()); repi(i, SZ(b)) b[i] = {ALL(b_[i])}; return b; } template struct has_e0 : false_type {}; template struct has_e0> : true_type {}; template inline constexpr bool has_e0_v = has_e0::value; template struct MonoidAdd { using S = T; }; template struct MonoidMin { using S = T; }; template struct MonoidMax { using S = T; }; namespace internal { template struct HasMonoidPow : false_type { }; template struct HasMonoidPow(), declval()))>> : true_type { }; } constexpr array DRULgrid = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}}; constexpr array DRULplane = {{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}}; // https://github.com/miscalculation53/library/tree/wip/template/template_binsearch.hpp template struct is_random_access_iterator { static constexpr bool value = is_same_v< typename iterator_traits::iterator_category, random_access_iterator_tag >; }; template constexpr bool is_random_access_iterator_v = is_random_access_iterator::value; #define DEFAULT_COMP ranges::less namespace internal { }; // https://github.com/miscalculation53/library/tree/wip/template/template_bit.hpp template inline constexpr ull MASK(T k) { return (1ULL << k) - 1ULL; } inline constexpr ll bit_width(ll x) { return std::bit_width((ull)x); } inline constexpr ll bit_floor(ll x) { return std::bit_floor((ull)x); } inline constexpr ll bit_ceil(ll x) { return std::bit_ceil((ull)x); } inline constexpr ll countr_zero(ll x) { assert(x != 0); return std::countr_zero((ull)x); } inline constexpr ll popcount(ll x) { return std::popcount((ull)x); } inline constexpr bool has_single_bit(ll x) { return std::has_single_bit((ull)x); } inline constexpr ull lsb_pos(ull x) { assert(x != 0); return countr_zero(x); } inline constexpr ull msb_pos(ull x) { assert(x != 0); return bit_width(x) - 1; } inline constexpr ull lsb_mask(ull x) { assert(x != 0); return x & -x; } inline constexpr ull msb_mask(ull x) { assert(x != 0); return bit_floor(x); } inline constexpr bool btest(ull x, uint k) { return (x >> k) & 1; } inline constexpr bool bsubset(ull x, ull y) { return (x & y) == x; } inline constexpr bool bsupset(ull x, ull y) { return (x & y) == y; } inline constexpr ull bsetminus(ull x, ull y) { return x & ~y; } // https://github.com/miscalculation53/library/tree/wip/template/template_inout.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_dump.hpp // https://github.com/miscalculation53/library/tree/wip/template/template_dump_map.hpp #define CPP_DUMP_DEFINE_DATA(...) #define dump(...) #define local(...) #define oj(...) __VA_ARGS__ #define local_oj(a,b) (b) namespace internal { template void CIN(Ts &...a) { (cin >> ... >> a); } template void READnodump(Ts &...a) { CIN(a...); } }; #define READ(...) internal::READnodump(__VA_ARGS__); dump(__VA_ARGS__) #define IN(T,...) T __VA_ARGS__; READ(__VA_ARGS__) #define CHAR(...) IN(char, __VA_ARGS__) #define INT(...) IN(int, __VA_ARGS__) #define LL(...) IN(ll, __VA_ARGS__) #define STR(...) IN(string, __VA_ARGS__) #define ARR(T,n,...) array __VA_ARGS__; READ(__VA_ARGS__) #define READVEC(...) internal::READVECnodump(__VA_ARGS__); dump(__VA_ARGS__) #define READVEC2(...) internal::READVEC2nodump(__VA_ARGS__); dump(__VA_ARGS__) #define VEC(T,n,...) vc __VA_ARGS__; READVEC(n, __VA_ARGS__) #define VEC2(T,n,m,...) vvc __VA_ARGS__; READVEC2(n, m, __VA_ARGS__) #define READJAG(...) internal::READJAGnodump(__VA_ARGS__); dump(__VA_ARGS__) #define JAG(T,n,...) vvc __VA_ARGS__; READJAG(n, __VA_ARGS__) #define ENDL endl template ostream &operator<<(ostream &os, const pair &p); template ostream &operator<<(ostream &os, const tuple &t); template ostream &operator<<(ostream &os, const array &a); template ostream &operator<<(ostream &os, const vc &v); namespace internal { template void COUTP(const Ts &...a) { if constexpr (sizeof...(Ts)) { int i = 0; ((cout << (i++ ? " " : "") << a), ...); } cout << ENDL; } }; #define WRITE internal::COUTW #define PRINT internal::COUTP #define PRINTEXIT(...) do { PRINT(__VA_ARGS__); exit(0); } while (false) #define PRINTRETURN(...) do { PRINT(__VA_ARGS__); return; } while (false) #define PRINTVEXIT(...) do { PRINTV(__VA_ARGS__); exit(0); } while (false) #define PRINTVRETURN(...) do { PRINTV(__VA_ARGS__); return; } while (false) namespace internal { }; namespace internal { }; #define UNZIP(vt,...) auto [__VA_ARGS__] = unzip(vt) #define ZIP(vt,...) auto vt = zip(tuple{__VA_ARGS__}) // https://github.com/miscalculation53/library/tree/wip/template/template_random.hpp mt19937_64 mt; bool randbool(double p) { assert(0 <= p && p <= 1); return bernoulli_distribution(p)(mt); } namespace internal { }; // https://github.com/miscalculation53/library/tree/wip/math/modint/template_modint.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/modint.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_static.hpp // https://github.com/miscalculation53/library/tree/wip/utils/larger_int.hpp namespace larger_int_detail { } template struct larger_int { private: static constexpr bool check(); static_assert(check()); public: using type = T; }; #define LARGER_INT(T,U) template <> struct larger_int { using type = U; }; LARGER_INT(signed char, short) LARGER_INT(short, int) LARGER_INT(int, long long) LARGER_INT(long, __int128_t) LARGER_INT(long long, __int128_t) LARGER_INT(unsigned char, unsigned short) LARGER_INT(unsigned short, unsigned int) LARGER_INT(unsigned int, unsigned long long) LARGER_INT(unsigned long, __uint128_t) LARGER_INT(unsigned long long, __uint128_t) #undef LARGER_INT template struct Rational; template struct larger_int> { using type = Rational::type>; }; template using larger_int_t = typename larger_int::type; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_isprime.hpp namespace internal { template constexpr ll powmod_constexpr(ll x, ll n, T m) { if (m == 1) return 0; using U = make_unsigned_t; using L = larger_int_t; U r = 1, y = safemod(x, m); while (n) { if (n & 1) r = L(r) * y % m; y = L(y) * y % m; n >>= 1; } return r; } template constexpr bool isprime = isprime_constexpr(n); }; namespace internal { template struct policy_static { using mod_type = decltype(M); using value_type = make_unsigned_t; using calc_type = larger_int_t; static constexpr bool is_prime = isprime_constexpr(M); static constexpr value_type init(value_type v) { return v; } static constexpr mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_barrett32.hpp namespace internal { struct barrett32 { uint m; ull im; explicit barrett32(uint m) : m(m), im((ull)(-1) / m + 1) {} uint umod() const { return m; } uint mul(uint a, uint b) const { ull z = a; z *= b; ull x = ull((u128(z) * im) >> 64); ull y = x * m; return uint(z - y + (z < y ? m : 0)); } }; template struct policy_barrett32 { using value_type = uint; using calc_type = ull; using mod_type = int; static constexpr bool is_prime = false; static inline barrett32 reducer{998244353}; static value_type init(value_type v) { return v; } static mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/modint_internal_montgomery64.hpp namespace internal { inline constexpr ull inv64(ull a) { ull x = a; while (a * x != 1) x *= 2 - a * x; return x; } struct montgomery64odd { ull m, im, sq; explicit montgomery64odd(ull m) : m(m), im(inv64(m)), sq(-u128(m) % m) {} ull umod() const { return m; } ull reduce(u128 x) const { auto t = (x + u128(m) * (-im * ull(x))) >> 64; if (t >= m) t -= m; return (ull)t; } ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * sq); } }; struct montgomery64 { ull m, mx, imx, d, q; uint b; explicit montgomery64(ull m) : m(m) { b = countr_zero(m), mx = m >> b; imx = inv64(mx); d = powmod_constexpr((mx + 1) / 2, b, mx); u128 sq = -u128(mx) % mx; q = (1 + (((sq - 1) * d) << b)) % m; } ull umod() const { return m; } ull reduce(u128 x) const { if (b == 0) { auto t = (x + u128(mx) * (-imx * ull(x))) >> 64; if (t >= m) t -= m; return (ull)t; } ull p = x & MASK(b); x = (x >> b) + p * d; ull y = p << (64 - b); auto t = (x + u128(mx) * (imx * (y - ull(x)))) >> (64 - b); if (t >= m) { t -= m; if (t >= m) t -= m; } return (ull)t; } ull inv_reduce(i128 v) const { return reduce(u128(v % m + m) * q); } }; template struct policy_montgomery64_odd { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64odd reducer{(1LL << 61) - 1}; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v); }; template struct policy_montgomery64 { using value_type = ull; using calc_type = u128; using mod_type = ll; static constexpr bool is_prime = false; static inline montgomery64 reducer{(1LL << 61) - 1}; static value_type init(value_type v) { return reducer.inv_reduce(v); } static mod_type val(value_type v); }; }; // https://github.com/miscalculation53/library/tree/wip/math/extgcd.hpp namespace internal { template struct modint_impl { using V = typename Policy::value_type; using M = typename Policy::mod_type; using mint = modint_impl; private: V _v; public: modint_impl(); template >> modint_impl(T v); M val() const; friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; } friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; } friend M safe_hash_key(const mint &x) { return x.val(); } friend std::istream &operator>>(std::istream &is, mint &x) { long long a; is >> a; x = a; return is; } friend std::ostream &operator<<(std::ostream &os, const mint &x) { os << x.val(); return os; } }; }; template using static_modint32 = internal::modint_impl>; template using dynamic_modint32 = internal::modint_impl>; template using static_modint64 = internal::modint_impl>; template using dynamic_modint64_odd = internal::modint_impl>; template using dynamic_modint64 = internal::modint_impl>; using modint998244353 = static_modint32<998244353>; template struct is_modint : std::false_type { }; template struct is_modint> : std::true_type { }; template inline constexpr bool is_modint_v = is_modint::value; template struct is_static_modint : false_type {}; template struct is_static_modint> : true_type {}; template struct is_static_modint> : true_type {}; template inline constexpr bool is_static_modint_v = is_static_modint::value; template struct is_dynamic_modint : false_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template struct is_dynamic_modint> : true_type {}; template inline constexpr bool is_dynamic_modint_v = is_dynamic_modint::value; // https://github.com/miscalculation53/library/tree/wip/math/modint/power_table.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/binomial.hpp template struct Binomial { private: inline static decltype(T::mod()) mod; public: inline static vc fac_, finv_, inv_; }; // https://github.com/miscalculation53/library/tree/wip/math/modint/stom.hpp // https://github.com/miscalculation53/library/tree/wip/math/modint/to_rational.hpp // https://github.com/miscalculation53/library/tree/wip/math/svp2d.hpp namespace cpp_dump { template struct rat_value { T p, q; friend ostream &operator<<(ostream &os, const rat_value &x) { os << x.p; if (x.q != 1) os << '/' << x.q; return os; } }; struct mint_to_rat_fn { }; template struct rat_object { T value; }; template inline constexpr bool rat_is_map = false; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; template inline constexpr bool rat_is_map> = true; struct rat_closure : std::ranges::range_adaptor_closure { }; constexpr rat_closure rat() { return rat_closure{}; } } using mint = modint998244353; // using mint = modint1000000007; // using mint = static_modint<1000000000>; // using mint = modint; using bi = Binomial; void init() { oj(mt.seed(random_device()())); } // https://github.com/miscalculation53/library/tree/wip/ds/cumulative_sum/imos_2d.hpp // https://github.com/miscalculation53/library/tree/wip/algebra/algebra_basic_ops.hpp // https://github.com/miscalculation53/library/tree/wip/algebra/algebra_base.hpp template struct has_e1 : false_type {}; template struct has_e1> : true_type {}; template inline constexpr bool has_e1_v = has_e1::value; template struct GroupAddSub { using S = T; static constexpr S op(S a, S b) { return a + b; } static constexpr S e() { if constexpr (has_e0_v) return S::e0(); else return S{}; } static constexpr S inv(S a) { return -a; } }; template > struct Imos2D { using S = typename G::S; private: vvc d; public: Imos2D(int n, int m) : d(n, vc(m, G::e())) {} void add(int li, int ri, int lj, int rj, const S &v) { if (d.empty()) return; const int n = d.size(), m = d[0].size(); assert(0 <= li && li <= ri && ri <= n); assert(0 <= lj && lj <= rj && rj <= m); if (li >= ri || lj >= rj) return; d[li][lj] = G::op(d[li][lj], v); S iv = G::inv(v); if (ri >= n) { if (rj < m) d[li][rj] = G::op(d[li][rj], iv); return; } d[ri][lj] = G::op(d[ri][lj], iv); if (rj >= m) return; d[li][rj] = G::op(d[li][rj], iv); d[ri][rj] = G::op(d[ri][rj], v); } vvc content() { if (d.empty()) return {}; const int n = d.size(), m = d[0].size(); vvc a(d); repi(i, n) repi(j, m - 1) a[i][j + 1] = G::op(a[i][j + 1], a[i][j]); repi(j, m) repi(i, n - 1) a[i + 1][j] = G::op(a[i + 1][j], a[i][j]); return a; } }; void main2() { LL(H, W, N); Imos2D imos(H, W); rep(_, N) { LL(li, lj, ri, rj); li--, lj--; imos.add(li, ri, lj, rj, 1); } auto res = imos.content(); dump(res); ll ans = 0; rep(i, H) rep(j, W) if (res[i][j] == 0) ans++; PRINT(ans); } void test() { } // https://github.com/miscalculation53/library/tree/wip/template/template_main.hpp template struct Main { Main() { cauto CERR = [](string val, string color) { string s = "\033[" + color + "m" + val + "\033[m"; }; cout << fixed << setprecision(20); init(); CERR("\n[SINGLE_TESTCASE]\n\n", "36"); main2(); } }; Main main_dummy; } int main() {}