#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 2e5 + 5;
int n, m, k, u[lim], d[lim], l[lim], r[lim], c[lim];
ll x;
namespace sub1{
void solve(){
for(int i = 1, min_x = n, max_x = 0, min_y = m, max_y = 0; i <= k; i++){
minimize(min_x, u[i]);
maximize(max_x, d[i]);
minimize(min_y, l[i]);
maximize(max_y, r[i]);
cout << ll(max_x - min_x + 1) * (max_y - min_y + 1) << "\n";
}
}
}
namespace sub23{
const ll INF = 2e14 + 36;
struct Node{
int lc, rc;
ll lazy, min_v, max_v;
Node(){
lc = rc = -1;
min_v = max_v = lazy = 0;
}
};
vector<Node>st(1);
int cur_min, cur_max;
void propagate(int id, ll icr){
st[id].min_v += icr;
maximize(st[id].min_v, -INF);
st[id].max_v += icr;
maximize(st[id].max_v, -INF);
st[id].lazy += icr;
maximize(st[id].lazy, -INF);
}
void push_down(int id){
propagate(st[id].lc, st[id].lazy);
propagate(st[id].rc, st[id].lazy);
st[id].lazy = 0;
}
void update(int id, int l, int r, int u, int v, int icr){
if(l > v || r < u || st[id].min_v >= x){
return;
}
if(u <= l && v >= r){
propagate(id, icr);
return;
}
if(st[id].lc == -1){
st[id].lc = st.size();
st.push_back(Node());
}
if(st[id].rc == -1){
st[id].rc = st.size();
st.push_back(Node());
}
int m = (l + r) >> 1;
push_down(id);
update(st[id].lc, l, m, u, v, icr);
update(st[id].rc, m + 1, r, u, v, icr);
st[id].min_v = min(st[st[id].lc].min_v, st[st[id].rc].min_v);
st[id].max_v = max(st[st[id].lc].max_v, st[st[id].rc].max_v);
}
void refine(int id, int l, int r){
if(st[id].max_v < x){
return;
}
if(st[id].min_v >= x){
minimize(cur_min, l);
maximize(cur_max, r);
propagate(id, -INF);
return;
}
int m = (l + r) >> 1;
push_down(id);
refine(st[id].lc, l, m);
refine(st[id].rc, m + 1, r);
st[id].min_v = min(st[st[id].lc].min_v, st[st[id].rc].min_v);
st[id].max_v = max(st[st[id].lc].max_v, st[st[id].rc].max_v);
}
namespace sub2{
void solve(){
cur_min = n;
cur_max = 0;
for(int i = 1; i <= k; i++){
update(0, 1, n, u[i], d[i], c[i]);
refine(0, 1, n);
cout << max(0, cur_max - cur_min + 1) << "\n";
}
}
}
namespace sub3{
void solve(){
vector<int>dx(u + 1, u + k + 1);
for(int i = 1; i <= k; i++){
dx.push_back(d[i] + 1);
}
sort(dx.begin(), dx.end());
dx.resize(unique(dx.begin(), dx.end()) - dx.begin());
vector<int>min_x(k + 1, n), max_x(k + 1, 0), min_y(k + 1, m), max_y(k + 1, 0);
for(int i = 0; i + 1 < dx.size(); i++){
st.assign(1, Node());
cur_min = m;
cur_max = 0;
for(int j = 1; j <= k; j++){
if(u[j] <= dx[i] && d[j] >= dx[i]){
update(0, 0, m, l[j], r[j], c[j]);
refine(0, 0, m);
}
if(cur_min <= cur_max){
minimize(min_y[j], cur_min);
maximize(max_y[j], cur_max);
minimize(min_x[j], dx[i]);
maximize(max_x[j], dx[i + 1] - 1);
}
}
}
for(int i = 1; i <= k; i++){
cout << ll(max(0, max_x[i] - min_x[i] + 1)) * max(0, max_y[i] - min_y[i] + 1) << "\n";
}
}
}
void solve(){
if(m == 1){
sub2::solve();
}
else{
sub3::solve();
}
}
}
void remove_duplicate(vector<int>& ve){
sort(ve.begin(), ve.end());
ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}
namespace sub45{
vector<int>dx(1, -1), dy(1, -1), ins[lim << 1], rem[lim << 1];
ll st[lim << 3], lazy[lim << 3];
int lid[lim], rid[lim];
void propagate(int id, ll x){
st[id] += x;
lazy[id] += x;
}
void push_down(int id){
propagate(id << 1, lazy[id]);
propagate(id << 1 | 1, lazy[id]);
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
propagate(id, x);
return;
}
int m = (l + r) >> 1;
push_down(id);
update(id << 1, l, m, u, v, x);
update(id << 1 | 1, m + 1, r, u, v, x);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int get_id_dx(int x){
return lower_bound(dx.begin(), dx.end(), x) - dx.begin();
}
int get_id_dy(int y){
return lower_bound(dy.begin(), dy.end(), y) - dy.begin();
}
pair<vector<int>, vector<int>>play(){
for(int i = 1; i < (lim << 1); i++){
ins[i].clear();
rem[i].clear();
}
for(int i = 1; i <= k; i++){
ins[get_id_dx(u[i])].push_back(i);
rem[get_id_dx(d[i])].push_back(i);
lid[i] = get_id_dy(l[i]);
rid[i] = get_id_dy(r[i]);
}
vector<int>min_x(k + 1, n), max_x(k + 1, 0);
memset(st, 0, sizeof(st));
memset(lazy, 0, sizeof(lazy));
set<int>set_qid;
int st_siz = dy.size();
for(int i = 1, limit_qid = k; i < dx.size(); i++){
for(int& id : ins[i]){
if(id <= limit_qid){
update(1, 1, st_siz, lid[id], rid[id], c[id]);
set_qid.insert(id);
}
}
while(limit_qid > 0 && st[1] >= x){
auto it = set_qid.find(limit_qid);
if(it == set_qid.end()){
limit_qid--;
}
else{
update(1, 1, st_siz, lid[limit_qid], rid[limit_qid], -c[limit_qid]);
if(st[1] < x){
update(1, 1, st_siz, lid[limit_qid], rid[limit_qid], c[limit_qid]);
break;
}
set_qid.erase(it);
limit_qid--;
}
}
if(st[1] >= x){
minimize(min_x[limit_qid], dx[i]);
}
for(int& id : rem[i]){
auto it = set_qid.find(id);
if(it != set_qid.end()){
update(1, 1, st_siz, lid[id], rid[id], -c[id]);
set_qid.erase(id);
}
}
}
for(int i = 1; i < k; i++){
minimize(min_x[i + 1], min_x[i]);
}
memset(st, 0, sizeof(st));
memset(lazy, 0, sizeof(lazy));
set_qid.clear();
for(int i = int(dx.size()) - 1, limit_qid = k; i > 0; i--){
for(int& id : rem[i]){
if(id <= limit_qid){
update(1, 1, st_siz, lid[id], rid[id], c[id]);
set_qid.insert(id);
}
}
while(limit_qid > 0 && st[1] >= x){
auto it = set_qid.find(limit_qid);
if(it == set_qid.end()){
limit_qid--;
}
else{
update(1, 1, st_siz, lid[limit_qid], rid[limit_qid], -c[limit_qid]);
if(st[1] < x){
update(1, 1, st_siz, lid[limit_qid], rid[limit_qid], c[limit_qid]);
break;
}
set_qid.erase(it);
limit_qid--;
}
}
if(st[1] >= x){
maximize(max_x[limit_qid], dx[i]);
}
for(int& id : ins[i]){
auto it = set_qid.find(id);
if(it != set_qid.end()){
update(1, 1, st_siz, lid[id], rid[id], -c[id]);
set_qid.erase(id);
}
}
}
for(int i = 1; i < k; i++){
maximize(max_x[i + 1], max_x[i]);
}
return make_pair(min_x, max_x);
}
void solve(){
for(int i = 1; i <= k; i++){
dx.push_back(u[i]);
dx.push_back(d[i]);
dy.push_back(l[i]);
dy.push_back(r[i]);
}
remove_duplicate(dx);
remove_duplicate(dy);
auto [min_x, max_x] = play();
for(int i = 1; i <= k; i++){
swap(u[i], l[i]);
swap(d[i], r[i]);
}
swap(n, m);
swap(dx, dy);
auto [min_y, max_y] = play();
for(int i = 1; i <= k; i++){
cout << ll(max(0, max_x[i] - min_x[i] + 1)) * max(0, max_y[i] - min_y[i] + 1) << "\n";
}
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> m >> k >> x;
for(int i = 1; i <= k; i++){
cin >> u[i] >> d[i] >> l[i] >> r[i] >> c[i];
}
if(x == 1){
sub1::solve();
}
else if(m == 1 || k <= 300){
sub23::solve();
}
else{
sub45::solve();
}
}
