C++ :

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

#define y1 safsdaf

const int N=101000;
int n,m,T,ty,x,y1,y2;
ll k,s;
pair<PII,int> range(ll l,ll s,ll k) {
	if (l>k) return mp(mp(0,-1),-1);
	if (s<l*(l+1)/2||s>l*(k+k-l+1)/2) return mp(mp(0,-1),-1);
	if (l==1) return mp(mp(s,s),-1);
	else if (l==k) return mp(mp(1,k),-1);
	else if (l==k-1) return mp(mp(1,k),k*(k+1)/2-s);
	else {
		ll mn=l*(l-1)/2,mk=(l-1)*(k+k-l+2)/2;
		if (s-mn==l) return mp(mp(1,l),-1);
		if (s-mn==l+1) return mp(mp(1,l+1),l);
		if (s-mk==k-l+1) return mp(mp(k-l+1,k),-1);
		if (s-mk==k-l) return mp(mp(k-l,k),k-l+1);
		PII rg=mp(1,k);
		if (s-mn<k) rg=mp(1,s-mn);
		else if (s-mk>1) rg=mp(s-mk,k);
		if (l>=3||(l==2&&s%2!=0)) return mp(rg,-1);
		else return mp(rg,s/2);
	}
}
struct event {
	int ty,x,y1,y2,l,r,del;
};
bool operator < (const event &a,const event &b) {
	return a.x<b.x||(a.x==b.x&&a.ty<b.ty);
}
vector<event> evt;

struct node {
	node *s[2];
	int s0; ll s1;
}pool[200*N],*cur=pool;
/// gai fan wei
node *newnode() {
	return cur++;
}
struct tnode {
	ll l0,r0,l1,r1;
	node *tl,*tr,*ban;
	unordered_map<int,int> del;
	void add(node* &p,int x,int s0,int s1) {
		int l=1,r=k;
		if (!p) p=newnode();
		node *t=p;
		while (1) {
			t->s0+=s0; t->s1+=s1;
			if (l==r) break;
			int md=(l+r)>>1;
			if (x<=md) {
				if (!t->s[0]) t->s[0]=newnode();
				t=t->s[0],r=md;
			}
			else {
				if (!t->s[1]) t->s[1]=newnode();
				t=t->s[1],l=md+1;
			}
		}
	}
	pair<int,ll> query(node *t,int x) {
		if (!t) return mp(0,0);
		if (x<=0) return mp(0,0);
		if (x==k) return mp(t->s0,t->s1);
		int l=1,r=k;
		int s0=0; ll s1=0;
		x++;
		while (1) {
			if (!t) break;
			int md=(l+r)>>1;
			if (x>md) {
				if (t->s[0]) s0+=t->s[0]->s0,s1+=t->s[0]->s1;
				l=md+1,t=t->s[1];

			}
			else r=md,t=t->s[0];
		}
		return mp(s0,s1);
	}
	int query(node *t,int l,int r,int tl,int tr) {
		if (!t) return 0;
		if (l==tl&&r==tr) return t->s0;
		int md=(l+r)>>1;
		if (tr<=md) return query(t->s[0],l,md,tl,tr);
		else if (tl>md) return query(t->s[1],md+1,r,tl,tr);
		else return query(t->s[0],l,md,tl,md)+query(t->s[1],md+1,r,md+1,tr);
	}
}nd[4*N];
void add(int p,int l,int r,int d,int w) {
	if (l>r) return;
	assert(l==1||r==k);
	for (;p<=n;p+=p&-p) {
		if (l<=d&&d<=r) 
			nd[p].del[d]+=w,nd[p].add(nd[p].ban,d,w,d*w);
		if (r==k) {
			nd[p].l0+=w;
			nd[p].l1+=w*l;
			nd[p].add(nd[p].tl,l,w,l*w);
		} else {
			nd[p].r0+=w;
			nd[p].r1+=w*r;
			nd[p].add(nd[p].tr,r,w,r*w);
		}
	}
}
int query(int p,int d) {
	int r=0;
	r+=nd[p].r0-nd[p].query(nd[p].tr,d-1).fi;
	r+=nd[p].query(nd[p].tl,d).fi;
	if (nd[p].del.count(d)) r-=nd[p].del[d];
	return r;
}
ll query(int p,int l,int r,int d) {
	ll ret=0;
	for (;p;p-=p&-p) {
		if (r==k) {
			auto tmp=nd[p].query(nd[p].tl,l-1);
			ret+=nd[p].l0*(k+1)-(nd[p].l1-tmp.se+tmp.fi*l);
			tmp=nd[p].query(nd[p].tr,l-1);
			ret+=(nd[p].r1-tmp.se)-(nd[p].r0-tmp.fi)*(l-1);
			ret-=nd[p].query(nd[p].ban,1,k,l,r);
			if (l<=d&&d<=r) ret-=query(p,d);			
		} else {
			auto tmp=nd[p].query(nd[p].tr,r-1);
			ret+=tmp.se+(nd[p].r0-tmp.fi)*r;
			tmp=nd[p].query(nd[p].tl,r);
			ret+=tmp.fi*(r+1)-tmp.se;
			ret-=nd[p].query(nd[p].ban,1,k,l,r);
			if (l<=d&&d<=r) ret-=query(p,d);
		}
	}
	return ret;
}
map<int,pair<int,pair<PII,int>>> rgx[N],rgy[N];
vector<pair<PII,int>> sgx,sgy;
int main() {
	scanf("%d%d%lld%d",&n,&m,&k,&T);
	rep(i,0,T) {
		scanf("%d%d%d%d%lld",&ty,&x,&y1,&y2,&s);
		auto rg=range(y2-y1+1,s,k);
		if (rg.fi.fi>rg.fi.se) continue;
		if (ty==0) rgx[x][y2]=mp(y1,rg); else rgy[x][y2]=mp(y1,rg);
		if (y1==y2) {
			if (ty==0) sgx.pb(mp(mp(x,y1),s)); else sgy.pb(mp(mp(x,y1),s));
			continue;
		}
		if (ty==1) {
			evt.pb((event){2,x,y1,y2,rg.fi.fi,rg.fi.se,rg.se});
		} else {
			evt.pb((event){1,y1,x,x,rg.fi.fi,rg.fi.se,rg.se});
			evt.pb((event){3,y2,x,x,rg.fi.fi,rg.fi.se,rg.se});
		}
	}
	ll ret=0;
	for (auto p:sgx) {
		int x=p.fi.fi,y=p.fi.se;
		auto it=rgy[y].lower_bound(x);
		if (it==rgy[y].end()||it->se.fi>x) continue;
		int l=it->se.se.fi.fi,r=it->se.se.fi.se,ban=it->se.se.se;
		if (p.se>=l&&p.se<=r&&p.se!=ban) ret++;
	}
	for (auto p:sgy) {
		int x=p.fi.fi,y=p.fi.se;
		auto it=rgx[y].lower_bound(x);
		if (it==rgx[y].end()||it->se.fi>x) continue;
		if (it->fi==x&&it->se.fi==x) continue;
		int l=it->se.se.fi.fi,r=it->se.se.fi.se,ban=it->se.se.se;
		if (p.se>=l&&p.se<=r&&p.se!=ban) ret++;
	}
//	printf("%lld\n",ret);
	sort(all(evt));

	for (auto p:evt) {
		if (p.ty==1) add(p.y1,p.l,p.r,p.del,1);
		else if (p.ty==3) add(p.y1,p.l,p.r,p.del,-1);
		else {
			ll v=query(p.y2,p.l,p.r,p.del)-query(p.y1-1,p.l,p.r,p.del);
//			printf("ff %d %d %d %lld\n",p.x,p.y1,p.y2,v);
			ret+=v;
		}
	}
	printf("%lld\n",ret);
}