#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 2e6+6;
int n;
pii lz[MXN<<2];
void build(int l=0, int r=n, int id=1) {
lz[id] = {0, 1};
if(r-l == 1) return;
build(l, mid, lc);
build(mid, r, rc);
}
inline void apply(pii x, int id) {
if(x.X >= lz[id].X) {
if(lz[id].Y <= x.X) lz[id] = {x.X, x.X+1};
else lz[id] = {x.X, min(x.Y, lz[id].Y)};
}
else lz[id] = {min(lz[id].X, x.Y-1), min(x.Y, lz[id].Y)};
}
inline void push(int id) {
apply(lz[id], lc);
apply(lz[id], rc);
lz[id] = {-1, 100001};
}
void upd(int s, int e, pii x, int l=0, int r=n, int id=1) {
if(s>=r || l>=e) return;
if(s<=l && r<=e) {
apply(x, id);
return;
}
push(id);
upd(s, e, x, l, mid, lc);
upd(s, e, x, mid, r, rc);
}
void print(int ans[], int l=0, int r=n, int id=1) {
if(r-l == 1) {
ans[l] = lz[id].X;
return;
}
push(id);
print(ans, l, mid, lc);
print(ans, mid, r, rc);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
::n = n;
build();
for(int i=0; i<k; i++)
if(op[i] == 1)
upd(left[i], right[i]+1, {height[i], 100001});
else
upd(left[i], right[i]+1, {-1, height[i]+1});
print(finalHeight);
}
