#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define pi pair<ll, ll>
#define pll pair<long long, long long>
#define vi vector<ll>
#define vll vector<long long>
#define vpi vector<pair<ll,ll>>
#define vpll vector<pair<long long, long long>>
#define pb push_back
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define forall(it,x) for(auto& it:(x))
#define mp make_pair
pi operator+(pi a, pi b) { return mp(a.ff+b.ff, a.ss+b.ss); }
pi operator-(pi a, pi b) { return mp(a.ff-b.ff, a.ss-b.ss); }
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll base = 1<<20;
struct SegTree {
vector<ll> T,L;
SegTree() {
T.assign(2*base,0);
L.assign(2*base,0);
}
void push(ll v, ll l, ll r) {
if(v>=base || L[v]==0) return;
for(auto x : {l,r}) {
L[x] += L[v];
T[x] += L[v];
}
L[v] = 0;
}
void update(ll v, ll a, ll b, ll p, ll k, ll val) {
if(p > k || b < p || k < a) return;
if(p<=a && b<=k) {
T[v] += val;
L[v] += val;
return;
}
ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
push(v,l,r);
update(l,a,mid,p,k,val);
update(r,mid+1,b,p,k,val);
T[v] = max(T[l], T[r]);
}
};
struct Rect {
ll u,d,l,r,c;
};
ll inf = 1;
ll X;
vector<ll> calc_left(vector<Rect> rec) {
ll n = rec.size();
vector<ll> Y;
for(auto&[u,d,l,r,c] : rec) {
Y.push_back(u);
Y.push_back(d);
}
sort(Y.begin(), Y.end());
for(auto&[u,d,l,r,c] : rec) {
u = lower_bound(Y.begin(), Y.end(), u) - Y.begin();
d = lower_bound(Y.begin(), Y.end(), d) - Y.begin();
}
vector<ll> res(n, -inf);
vector<pair<ll, ll>> sweep;
for(ll i=0; i<n; ++i) {
sweep.emplace_back(rec[i].l, -i);
sweep.emplace_back(rec[i].r, i+1);
}
ll idx = n-1;
sort(sweep.begin(), sweep.end());
SegTree st;
vector<ll> opened(n);
for(auto[x, i] : sweep) {
if(i > 0) {
--i;
// cerr << " - " << i << "\n";
if(i > idx) continue;
st.update(1,0,base-1,rec[i].u, rec[i].d, -rec[i].c);
opened[i] = 0;
} else {
i*=-1;
// cerr << " + " << i << "\n";
if(i > idx) continue;
st.update(1,0,base-1,rec[i].u, rec[i].d, rec[i].c);
opened[i] = 1;
while(st.T[1] >= X && idx >= 0) {
if(opened[idx]) {
st.update(1,0,base-1,rec[idx].u, rec[idx].d, -rec[idx].c);
opened[idx] = 0;
}
res[idx] = x;
idx--;
}
}
}
return res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll h, w, n;
cin >> h >> w >> n >> X;
vector<Rect> pro(n);
for(auto&[u,d,l,r,c] : pro) {
cin >> u >> d >> l >> r >> c;
}
vector<ll> left = calc_left(pro);
for(auto&[u,d,l,r,c] : pro) {
l = w-l;
r = w-r;
swap(l,r);
}
vector<ll> right = calc_left(pro);
for(auto &x : right) if(x != -1) x = w-x;
for(auto&[u,d,l,r,c] : pro) {
l = w-l;
r = w-r;
swap(l,r);
}
for(auto&[u,d,l,r,c] : pro) {
swap(u,l);
swap(r,d);
}
vector<ll> upper = calc_left(pro);
for(auto&[u,d,l,r,c] : pro) {
swap(u,l);
swap(r,d);
}
for(auto&[u,d,l,r,c] : pro) {
u = h-u;
d = h-d;
swap(u,d);
}
for(auto&[u,d,l,r,c] : pro) {
swap(u,l);
swap(r,d);
}
vector<ll> lower = calc_left(pro);
for(auto &x : lower) x = h-x;
// for(auto x : left) cout << x << " "; cout << "\n";
// for(auto x : right) cout << x << " "; cout << "\n";
// for(auto x : upper) cout << x << " "; cout << "\n";
// for(auto x : lower) cout << x << " "; cout << "\n";
for(ll i=0; i<n; ++i) {
if(left[i] == -inf) {
cout << "0\n";
} else {
cout << (right[i] - left[i] + 1)*(lower[i] - upper[i] + 1) << "\n";
}
}
return 0;
}
