#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
struct LazySegtree {
vector<ll> A;
vector<ll> B;
int N;
LazySegtree(ll n) {
N = 1;
while (N < n) N *= 2;
A.assign(N * 2, 0);
B.assign(N * 2, 0);
}
void apply_node(ll i, ll a) {
B[i] += a;
A[i] += a;
}
void push(ll i) {
if (i < N) {
apply_node(i * 2, B[i]);
apply_node(i * 2 + 1, B[i]);
B[i] = 0;
}
}
void aggr(ll i) {
A[i] = max(A[i * 2], A[i * 2 + 1]);
}
void apply_rec(ll l, ll r, ll a, ll pl, ll pr, ll i) {
if (r <= pl || pr <= l) return;
if (l <= pl && pr <= r) {
apply_node(i, a);
return;
}
push(i);
apply_rec(l, r, a, pl, (pl + pr) / 2, i * 2);
apply_rec(l, r, a, (pl + pr) / 2, pr, i * 2 + 1);
aggr(i);
}
void apply(ll l, ll r, ll a) {
apply_rec(l, r, a, 0, N, 1);
}
ll get() {
return A[1];
}
};
vector<ll> argmin_x_no_less_than_X(
ll N,
const vector<ll>& U,
const vector<ll>& D,
const vector<ll>& L,
const vector<ll>& R,
const vector<ll>& C,
ll X
) {
vector<ll> posY;
for (ll i = 0; i < N; i++) {
posY.push_back(U[i]);
posY.push_back(D[i]);
}
sort(posY.begin(), posY.end());
vector<pair<ll, ll>> events;
for (ll i = 0; i < N; i++) {
events.push_back({ L[i], N + i });
events.push_back({ R[i], i });
}
sort(events.begin(), events.end());
LazySegtree ds(posY.size());
vector<ll> entered(N);
vector<ll> ans(N, -1);
ll T = N - 1;
auto add = [&](ll u, ll d, ll c) -> void {
u = lower_bound(posY.begin(), posY.end(), u) - posY.begin();
d = lower_bound(posY.begin(), posY.end(), d) - posY.begin();
ds.apply(u, d, c);
};
for (auto [t, ev] : events) {
if (ev < N) {
ll e = ev;
if (entered[e]) {
add(U[e], D[e], -C[e]);
entered[e] = 0;
}
}
else {
ll e = ev - N;
if (e <= T) {
add(U[e], D[e], C[e]);
entered[e] = 1;
}
while (ds.get() >= X) {
ans[T] = t;
if (entered[T]) {
add(U[T], D[T], -C[T]);
entered[T] = 0;
}
T--;
}
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll H, W, N, X;
cin >> H >> W >> N >> X;
vector<ll> L(N), R(N), U(N), D(N), C(N);
for (ll i = 0; i < N; i++) {
cin >> U[i] >> D[i] >> L[i] >> R[i] >> C[i];
U[i]--;
L[i]--;
}
vector<vector<ll>> result;
for (ll dir = 0; dir < 4; dir++) {
result.push_back(argmin_x_no_less_than_X(N, U, D, L, R, C, X));
for (ll i = 0; i < N; i++) {
L[i] = W - L[i];
R[i] = W - R[i];
}
swap(L, U);
swap(U, R);
swap(R, D);
swap(H, W);
}
vector<ll> ans(N);
for (ll i = 0; i < N; i++) {
if (result[0][i] != -1) {
ans[i] = (W - result[0][i] - result[2][i]) * (H - result[1][i] - result[3][i]);
}
}
for (ll i = 0; i < N; i++) {
cout << ans[i] << "\n";
}
return 0;
}
