#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<string>#include<map>#include<set>#include<iostream>#include<vector>#include<queue>using namespace std;#define sz(v) ((int)(v).size())#define rep(i, n) for (lint i = 0; i < (n); ++i)#define repf(i, a, b) for (lint i = (a); i <= (b); ++i)#define repd(i, a, b) for (lint i = (a); i >= (b); --i)#define clr(x) memset(x,0,sizeof(x))#define clrs( x , y ) memset(x,y,sizeof(x))typedef long long lint;const lint maxlint = -1u>>1;const double esp = 1e-8;const lint maxn = 50000 + 10;lint W, H, N, M;struct node{ lint sx, sy, ex, ey; void input(){ scanf("%lld%lld%lld%lld", &sx, &sy, &ex, &ey); }}a[maxn];struct node2{ lint l, r, ty, y; bool operator < (const node2& a) const { if(y != a.y) return y < a.y; else return ty > a.ty; }}; vector<node2> b;vector<lint> xx;map<lint, lint> mpx;lint sum[maxn * 4 * 4], lazy[maxn * 4 * 4];lint max(lint x, int y){ if(x > y) return x; else return y; }void init(){ rep(i, N){ a[i].input(); }}void get_ch(lint t, lint &lc, lint &rc){ lc = t << 1; rc = (t << 1) | 1;}void build(lint t, lint l, lint r){ lint lc, rc, mid; mid = (l + r) >> 1; get_ch(t, lc, rc); sum[t] = 0; lazy[t] = 0; if(l != r){ build(lc, l, mid); build(rc, mid + 1, r); }}void push_down(const lint &t, const lint& lc, const lint& rc){ lazy[lc] += lazy[t]; lazy[rc] += lazy[t]; lazy[t] = 0;} void push_up(const lint &t, const lint&lc, const lint& rc){ sum[t] = sum[lc] + sum[rc];} void add(lint t, lint l, lint r, lint x, lint y, lint ty){ if(x > y || r < x || y < l) return; lint lc, rc, mid; mid = (l + r) >> 1; get_ch(t, lc, rc); if(x <= l && r <= y){ lazy[t] += ty; if(lazy[t] > 0) sum[t] = xx[r + 1] - xx[l]; else if(l == r) sum[t] = 0; else sum[t] = sum[lc] + sum[rc]; } else{ add(lc, l, mid, x, y, ty); add(rc, mid + 1, r, x, y, ty); if(lazy[t] > 0) sum[t] = xx[r + 1] - xx[l]; else sum[t] = sum[lc] + sum[rc]; }}lint gao(const vector<lint>& xx, map<lint, lint>& mpx, const vector<node2> &b){ lint len = sz(xx) - 1; lint res = 0; if(sz(b) == 0) return 0; build(1, 0, len); rep(i, sz(b) - 1){ add(1, 0, len, mpx[ b[i].l ], mpx[ b[i].r + 1] - 1, b[i].ty); res += sum[1] * (b[i + 1].y - b[i].y); } return res;}void get_bx(vector<node2>& b, node *a){ b.clear(); xx.clear(); mpx.clear(); rep(i, N){ node2 now; now.l = max(a[i].sx - (M - 1), 1); now.r = min(a[i].ex, W - (M - 1)); xx.push_back(now.l); xx.push_back(now.r); xx.push_back(now.l + 1); xx.push_back(now.r + 1); now.ty = 1; now.y = a[i].sy; b.push_back(now); now.l = max(a[i].sx - (M - 1), 1); now.r = min(a[i].ex, W - (M - 1)); now.ty = -1; now.y = a[i].ey + 1; b.push_back(now); } sort(b.begin(), b.end()); sort(xx.begin(), xx.end()); xx.erase(unique(xx.begin(), xx.end()), xx.end()); mpx.clear(); rep(i, sz(xx)) mpx[ xx[i] ] = i;}void get_by(vector<node2>& b, node *a){ b.clear(); xx.clear(); mpx.clear(); rep(i, N){ node2 now; now.l = max(a[i].sy - (M - 1), 1); now.r = min(a[i].ey, H - (M - 1)); xx.push_back(now.l); xx.push_back(now.r); xx.push_back(now.l + 1); xx.push_back(now.r + 1); now.ty = 1; now.y = a[i].sx; b.push_back(now); now.l = max(a[i].sy - (M - 1), 1); now.r = min(a[i].ey, H - (M - 1)); now.ty = -1; now.y = a[i].ex + 1; b.push_back(now); } sort(b.begin(), b.end()); sort(xx.begin(), xx.end()); xx.erase(unique(xx.begin(), xx.end()), xx.end()); if(sz(xx) != 0) xx.push_back(xx[sz(xx) - 1] + 1); mpx.clear(); rep(i, sz(xx)) mpx[ xx[i] ] = i;}void gao(){ lint xm, ym, ans; get_bx(b, a); xm = (W - (M - 1)) * H - gao(xx, mpx, b); get_by(b, a); ym = W * (H - (M - 1)) - gao(xx, mpx, b); xm = max(xm, 0); ym = max(ym, 0); ans = xm + ym; if(M == 1) ans /= 2; printf("%lldn", ans);}int main(){ while(scanf("%lld%lld%lld%lld", &W, &H, &N, &M) != EOF){ init(); gao(); } return 0;}
