1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 #include<cstdio>
5 #include<cassert>
6 using namespace std;
7 typedef
long long ll;
8 template <typename T> inline
void chkmax(T &a,
const T b){
if(a < b) a=b;}
9 template <typename T> inline
void chkmin(T &a,
const T b){
if(a > b) a=b;}
10 const int N = 100005;
11 int lt[N<<2],rt[N<<2],cnt[N<<2];
12 int w,h,n,m,L,R;
13 int X[N],num[N][4];
14 struct node{
15 int l,r,h,p;
16 node(){}
17 node(
int L,
int R,
int H,
int P):l(L),r(R),h(H),p(P){}
18 bool operator < (
const node &A)
const {
19 return h == A.h? p < A.p: h < A.h;
20 }
21 } seg[N];
22 // segment_tree
23 inline
void upt(
int pos,
int l,
int r){
24 assert(!cnt[pos] && l<r);
25 lt[pos] = lt[pos<<1] == -1 ? lt[pos<<1|1] : lt[pos<<1];
26 rt[pos] = rt[pos<<1|1] == -1 ? rt[pos<<1] : rt[pos<<1|1];
27 }
28 void update(
int l,
int r,
int pos,
int ML,
int MR,
int ct){
29 if(r >= MR && l <= ML){
30 cnt[pos] += ct;
31 if(cnt[pos]) lt[pos] = ML==l? l:-1, rt[pos] = MR == r ? r:-1;
32 else lt[pos] = rt[pos] = -1;
33 return;
34 }
35 int mid = ML + MR >>1;
36 if(mid >= l) update(l,r,pos<<1,ML,mid,ct);
37 else chkmax(R,rt[pos<<1]);
38 if(mid < r) update(l,r,pos<<1|1,mid+1,MR,ct);
39 else if(lt[pos<<1|1]!=-1) chkmin(L,lt[pos<<1|1]);
40 upt(pos,ML,MR);
41 }
42 // sweep line
43 ll cal(
int len,
int m){
44 if(m>len)
return 0;
45 return len -m + 1;
46 }
47 int search(
int val,
int n){
48 int l =0, r = n;
49 while(l<r){
50 int mid = l + r>>1;
51 if(X[mid]>=val) r = mid;
52 else l = mid+1;
53 }
54 return l;
55 }
56 ll work(){
57 int len = 0,k = 1;
58 for(
int i=0;i<n;i++){
59 seg[len] = node(num[i][0],num[i][2],num[i][1]-1,1);
60 X[len++] = num[i][0];
61 seg[len] = node(num[i][0],num[i][2],num[i][3],-1);
62 X[len++] = num[i][2];
63 }
64 sort(seg,seg+len);
65 sort(X,X+len);
66 for(
int i=1;i<len;i++)
67 if(X[i]!=X[i-1]) X[k++] = X[i];
68 for(
int i=k;i>=1;i--) X[i] = X[i-1];
69 memset(lt,-1,
sizeof(lt));
70 memset(rt,-1,
sizeof(rt));
71 memset(cnt,0,
sizeof(cnt));
72 X[0] = 0; X[k+1] = w+1;
73 update(0,0,1,0,k+1,1);
74 update(k+1,k+1,1,0,k+1,1);
75 ll last = cal(w,m);
76 ll ans = last * seg[0].h;
77 for(
int i=0;i<len-1;i++){
78 int l = search(seg[i].l,k+1);
79 int r = search(seg[i].r,k+1);
80 L = w+1, R = -1;
81 update(l,r,1,0,k+1,seg[i].p);
82 last -= seg[i].p * cal(X[L]-X[R]-1,m);
83 last += seg[i].p * cal(X[L]-X[r]-1,m);
84 last += seg[i].p * cal(X[l]-X[R]-1,m);
85 ans += last * (seg[i+1].h - seg[i].h);
86 }
87 ans += cal(w,m) * (h - seg[len-1].h);
88 return ans;
89 }
90 // main
91 int main(){
92 ll ans ;
93 while(~scanf("%d%d%d%d",&w,&h,&n,&m)){
94 for(
int i=0;i<n;i++)
for(
int j=0;j<4;j++)
95 scanf("%d",&num[i][j]);
96 if(n==0) {
97 ans = h*cal(w,m) + w*cal(h,m);
98 if(m == 1) cout<<ans/2<<endl;
99 else cout<<ans<<endl;
100 continue;
101 }
102 ans = work();
103 swap(w,h);
104 for(
int i=0;i<n;i++){
105 swap(num[i][0],num[i][1]);
106 swap(num[i][2],num[i][3]);
107 }
108 ans += work();
109 if(m==1)
110 cout<<ans/2<<endl;
111 else cout<<ans<<endl;
112 }
113 }
114