#include <bits/allocator.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N=2e5+10;
int h, w, q; long long xx;
array<int, 5> a[N];
vector<int> valx, valy;
struct Node{
int val, lazy;
Node(){ val=0, lazy=0; }
};
struct SegmentTree{
Node t[1<<21];
void init(int n){
fill(t, t+4*n, Node());
}
void apply(int k, long long x){
}
void push(int k){
if (t[k].lazy){
apply(k<<1, t[k].lazy);
apply(k<<1|1, t[k].lazy);
t[k].lazy=0;
}
}
void update(int k, int l, int r, int L, int R, int x){
if (r<L || R<l) return;
if (L<=l && r<=R){
t[k].val+=x;
t[k].lazy+=x;
return;
}
if (t[k].lazy){
t[k<<1].val+=t[k].lazy;
t[k<<1].lazy+=t[k].lazy;
t[k<<1|1].val+=t[k].lazy;
t[k<<1|1].lazy+=t[k].lazy;
t[k].lazy=0;
}
int mid=(l+r)>>1;
update(k<<1, l, mid, L, R, x);
update(k<<1|1, mid+1, r, L, R, x);
t[k].val=max(t[k<<1].val, t[k<<1|1].val);
}
};
int cc=0;
struct DS{
SegmentTree st;
vector<pair<int, int>> changes;
int ans;
set<int> stt;
void add(int x){
stt.insert(x);
changes.emplace_back(0, x);
if (x<ans){
changes.emplace_back(1, x);
st.update(1, 0, (int)valy.size()-1, a[x][2], a[x][3], a[x][4]);
++cc;
}
auto it=stt.lower_bound(ans);
while (1){
if (it!=stt.end()){
st.update(1, 0, (int)valy.size()-1, a[*it][2], a[*it][3], -a[*it][4]);
}
if (st.t[1].val>=xx){
if (it!=stt.end()){
changes.emplace_back(1, -(*it));
}
changes.emplace_back(2, ans);
--it;
ans=(*it);
}else{
if (it!=stt.end()){
st.update(1, 0, (int)valy.size()-1, a[*it][2], a[*it][3], a[*it][4]);
}
break;
}
}
}
void rollback(int size){
while ((int)changes.size()>size){
auto t=changes.back();
changes.pop_back();
if (t.first==0) stt.erase(t.second);
else if (t.first==1){
int id=abs(t.second);
st.update(1, 0, (int)valy.size()-1, a[id][2], a[id][3], t.second>0?-a[id][4]:a[id][4]);
}else ans=t.second;
}
}
void init(){
st.init((int)valy.size());
changes.clear();
ans=1e9;
stt.clear();
}
} ds;
vector<int> fx, fy;
struct TimeSegmentTree{
vector<vector<int>> t;
void init(int n){
t.assign(4*n, {});
}
void update(int k, int l, int r, int L, int R, int val){
if (r<L || R<l) return;
if (L<=l && r<=R){
t[k].push_back(val);
return;
}
int mid=(l+r)>>1;
update(k<<1, l, mid, L, R, val);
update(k<<1|1, mid+1, r, L, R, val);
}
void dfs(int k, int l, int r){
int size=ds.changes.size();
for (auto &x:t[k]){
ds.add(x);
}
if (l==r){
fx[l]=ds.ans;
}else{
int mid=(l+r)>>1;
dfs(k<<1, l, mid);
dfs(k<<1|1, mid+1, r);
}
ds.rollback(size);
}
} tst;
int lx[N], rx[N], ly[N], ry[N];
void solvex(){
ds.init();
tst.init((int)valx.size());
for (int i=1; i<=q; ++i){
tst.update(1, 0, (int)valx.size()-1, a[i][0], a[i][1], i);
lx[i]=1e9; rx[i]=-1e9;
}
cc=0;
tst.dfs(1, 0, (int)valx.size()-1);
cerr << cc << '\n';
for (int i=0; i<(int)valx.size(); ++i){
if (fx[i]!=1e9){
lx[fx[i]]=min(lx[fx[i]], i);
rx[fx[i]]=max(rx[fx[i]], i);
}
}
for (int i=2; i<=q; ++i){
lx[i]=min(lx[i], lx[i-1]);
rx[i]=max(rx[i], rx[i-1]);
}
}
void solve(){
for (int i=1; i<=q; ++i){
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3] >> a[i][4];
valx.push_back(a[i][0]);
valx.push_back(a[i][1]);
valy.push_back(a[i][2]);
valy.push_back(a[i][3]);
}
sort(valx.begin(), valx.end());
valx.resize(unique(valx.begin(), valx.end())-valx.begin());
sort(valy.begin(), valy.end());
valy.resize(unique(valy.begin(), valy.end())-valy.begin());
for (int i=1; i<=q; ++i){
a[i][0]=lower_bound(valx.begin(), valx.end(), a[i][0])-valx.begin();
a[i][1]=lower_bound(valx.begin(), valx.end(), a[i][1])-valx.begin();
a[i][2]=lower_bound(valy.begin(), valy.end(), a[i][2])-valy.begin();
a[i][3]=lower_bound(valy.begin(), valy.end(), a[i][3])-valy.begin();
}
fx.resize(valx.size());
fy.resize(valy.size());
solvex();
valx.swap(valy);
fx.swap(fy);
swap(lx, ly);
swap(rx, ry);
for (int i=1; i<=q; ++i){
swap(a[i][0], a[i][2]);
swap(a[i][1], a[i][3]);
}
solvex();
for (int i=1; i<=q; ++i){
if (lx[i]>rx[i] || ly[i]>ry[i]) cout << 0 << '\n';
else cout << 1ll*(valx[rx[i]]-valx[lx[i]]+1)*(valy[ry[i]]-valy[ly[i]]+1) << '\n';
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("garden.inp", "r", stdin);
cin >> h >> w >> q >> xx;
solve();
return 0;
}
