#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct Data{
int lo, hi;
Data(int _lo = -1e9, int _hi = 1e9){
lo = _lo;
hi = _hi;
}
Data operator + (const Data &oth){
if (hi < oth.lo)
return Data(oth.lo, oth.lo);
if (oth.hi < lo)
return Data(oth.hi, oth.hi);
return Data(max(lo, oth.lo), min(hi, oth.hi));
}
};
struct SegTree{
int n;
vector<Data> d;
void build(int id, int l, int r){
if (l == r){
d[id] = Data(0, 0);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
void init(int _n){
n = _n;
d.assign(n * 4 + 1, Data(-1e9, 1e9));
build(1, 1, n);
}
void update(int id, int l, int r, int u, int v, Data val){
if (v < l || r < u)
return;
if (u <= l && r <= v){
d[id] = d[id] + val;
return;
}
d[id << 1] = d[id << 1] + d[id];
d[id << 1 | 1] = d[id << 1 | 1] + d[id];
d[id] = Data(-1e9, 1e9);
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
}
void solve(int id, int l, int r, int res[]){
if (l == r){
assert(d[id].lo == d[id].hi);
res[l - 1] = d[id].lo;
return;
}
d[id << 1] = d[id << 1] + d[id];
d[id << 1 | 1] = d[id << 1 | 1] + d[id];
d[id] = Data(-1e9, 1e9);
int mid = (l + r) >> 1;
solve(id << 1, l, mid, res);
solve(id << 1 | 1, mid + 1, r, res);
}
void update(int l, int r, Data val){
update(1, 1, n, l, r, val);
}
void solve(int res[]){
solve(1, 1, n, res);
}
} st;
void buildWall(int n, int k, int type[], int l[], int r[], int h[], int res[]){
st.init(n);
for(int i = 0; i < k; i++)
if (type[i] == 1)
st.update(l[i] + 1, r[i] + 1, Data(h[i], 1e9));
else
st.update(l[i] + 1, r[i] + 1, Data(-1e9, h[i]));
st.solve(res);
return;
}
