#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <climits>
using namespace std;
using ll = long long;
using db = long double;
using str = string;
using pi = pair <int, int>;
using pl = pair <ll, ll>;
using pd = pair <db, db>;
#define mp make_pair
#define ff first
#define ss second
template <class T> using V = vector <T>;
using vi = V <int>;
using vb = V <bool>;
using vl = V <ll>;
using vd = V <db>;
using vs = V <str>;
using vpi = V <pi>;
using vpl = V <pl>;
using vpd = V <pd>;
template <class T> using PQ = priority_queue <T>;
#define sz(x) (int) size(x)
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define srt(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define emb emplace_back
#define em emplace
#define ft front()
#define bk back()
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) FOR(i, 0, a-1)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define each(e, x) for (auto &e : x)
ll cdiv(ll a, ll b) { return ceil((db) a / b); }
ll fdiv(ll a, ll b) { return floor((db) a / b); }
template <typename T, typename = void>
struct is_iterable : false_type {};
template <typename T>
struct is_iterable<T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};
void err(string name) {}
template <typename T, typename... Args>
void err(string name, T val, Args... args) {
size_t pos = name.find(',');
string first = (pos == string::npos) ? name : name.substr(0, pos);
string rest = (pos == string::npos) ? "" : name.substr(pos + 2);
cout << first << " = ";
if constexpr (is_iterable<T>::value && !is_same_v<T, string>) {
cout << "{";
bool fst = true;
for (auto const& x : val) {
if (!fst) cout << ", ";
cout << x;
fst = false;
}
cout << "}";
} else {
cout << val;
}
if (rest != "") {
cout << " | ";
err(rest, args...);
} else {
cout << '\n';
}
}
#ifdef LOCAL
#define dbg(...) cout << "[" << __FUNCTION__ << ":" << __LINE__ << "] ", err(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...) 67
#endif
void setIO(string name = "") {
ios::sync_with_stdio(0), cin.tie(0);
if (sz(name)) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
const ll INF = 1e18;
const pi d[4] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353; // 1e9+7;
const int mxN = 2*2e5+5;
ll _, n, K;
vl cx, cy;
V <tuple <ll, ll, ll, ll, ll>> Q;
struct SEG {
ll seg[4*mxN], lz[4*mxN];
void build(int l, int r, int u) {
if (l == r) seg[u] = 0;
else {
int m = l + (r-l)/2;
build(l, m, u<<1);
build(m+1, r, u<<1|1);
seg[u] = lz[u] = 0;
}
}
void push(int u) {
seg[u<<1] += lz[u];
seg[u<<1|1] += lz[u];
lz[u<<1] += lz[u];
lz[u<<1|1] += lz[u];
lz[u] = 0;
}
void upd(int l, int r, int x, int y, ll k, int u) {
if (x <= l && r <= y) seg[u] += k, lz[u] += k;
else {
push(u);
int m = l + (r-l)/2;
if (m >= x) upd(l, m, x, y, k, u<<1);
if (m+1 <= y) upd(m+1, r, x, y, k, u<<1|1);
seg[u] = max(seg[u<<1], seg[u<<1|1]);
}
}
} T;
V <tuple <ll, ll, ll, ll>> A[mxN], A2[mxN];
int main() {
setIO();
cin >> _ >> _ >> n >> K;
Q.resize(n);
for (auto &[x1, x2, y1, y2, c] : Q) {
cin >> x1 >> x2 >> y1 >> y2 >> c;
cx.emb(x1), cx.emb(x2);
cy.emb(y1), cy.emb(y2);
}
srt(cx), srt(cy);
cx.rsz(unique(all(cx)) - bg(cx)), cy.rsz(unique(all(cy)) - bg(cy));
for (auto &[x1, x2, y1, y2, c] : Q) {
x1 = lower_bound(all(cx), x1) - bg(cx);
x2 = lower_bound(all(cx), x2) - bg(cx);
y1 = lower_bound(all(cy), y1) - bg(cy);
y2 = lower_bound(all(cy), y2) - bg(cy);
// cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << '\n';
}
auto fi = [&] () {
T.build(0, 2*n, 1);
int it = 0;
for (auto &e : A) e.clear();
for (auto &e : A2) e.clear();
for (auto &[x1, x2, y1, y2, c] : Q) {
A[x1].emplace_back(it, y1, y2, c);
A[x2+1].emplace_back(it, y1, y2, -c);
it++;
}
vl ans(n, -1);
// return ans;
it = n-1;
for (int i = 0; i < 2*n; i++) {
for (auto &[ii, y1, y2, c] : A[i]) if (ii <= it) {
T.upd(0, 2*n, y1, y2, c, 1);
A2[ii].emplace_back(ii, y1, y2, c);
}
while (T.seg[1] >= K && it >= 0) {
ans[it] = i;
for (auto &[ii, y1, y2, c] : A2[it]) {
T.upd(0, 2*n, y1, y2, -c, 1);
}
it--;
}
if (it < 0) break;
}
return ans;
};
vl a1, a2, b1, b2;
a1 = fi();
// return 0;
for (auto &[x1, x2, y1, y2, c] : Q) {
swap(x1, x2);
x1 = 2*n - x1 - 1;
x2 = 2*n - x2 - 1;
}
a2 = fi();
for (auto &e : a2) if (e > -1) e = 2*n - e - 1;
for (auto &[x1, x2, y1, y2, c] : Q) {
swap(x1, x2);
x1 = 2*n - x1 - 1;
x2 = 2*n - x2 - 1;
}
for (auto &[x1, x2, y1, y2, c] : Q) swap(x1, y1), swap(x2, y2);
b1 = fi();
for (auto &[x1, x2, y1, y2, c] : Q) {
swap(x1, x2);
x1 = 2*n - x1 - 1;
x2 = 2*n - x2 - 1;
}
b2 = fi();
for (auto &e : b2) if (e > -1) e = 2*n - e - 1;
for (auto &[x1, x2, y1, y2, c] : Q) {
swap(x1, x2);
x1 = 2*n - x1 - 1;
x2 = 2*n - x2 - 1;
}
for (auto &[x1, x2, y1, y2, c] : Q) swap(x1, y1), swap(x2, y2);
for (int i = 0; i < n; i++) {
// cout << a1[i] << ' ' << a2[i] << ' ' << b1[i] << ' ' << b2[i] << '\n';
if (a1[i] >= 0 && a2[i] >= 0 && b1[i] >= 0 && b2[i] >= 0) {
a1[i] = cx[a1[i]], a2[i] = cx[a2[i]];
b1[i] = cy[b1[i]], b2[i] = cy[b2[i]];
cout << (a2[i] - a1[i] + 1) * (b2[i] - b1[i] + 1) << '\n';
} else {
cout << 0 << '\n';
}
}
}
