#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
vector<int> ans;
struct SegTree {
int n;
vector<pair<pair<int, int>, pair<int, int>>> tree;
SegTree(int _n) {n=_n, tree.resize(4*n, {{-1, -1}, {-1, -1}});}
void add(int node, int h, int op) {
if (op==0) {
if (tree[node].fi.se==-1) tree[node].fi={h, op};
else if (tree[node].fi.se==op) cmax(tree[node].fi.fi, h);
else if (tree[node].se.se==-1) tree[node].se={h, op}, swap(tree[node].fi, tree[node].se);
else {
swap(tree[node].fi, tree[node].se);
tree[node].fi.fi=max(min(tree[node].se.fi, tree[node].fi.fi), h);
}
} else {
if (tree[node].fi.se==-1) tree[node].fi={h, op};
else if (tree[node].fi.se==op) cmin(tree[node].fi.fi, h);
else if (tree[node].se.se==-1) tree[node].se={h, op}, swap(tree[node].fi, tree[node].se);
else {
swap(tree[node].fi, tree[node].se);
tree[node].fi.fi=min(max(tree[node].se.fi, tree[node].fi.fi), h);
}
}
}
void propagate(int node, int l, int r) { if (l==r || tree[node].fi.se==-1) return;
if (tree[node].se.se!=-1) {
add(node*2, tree[node].se.fi, tree[node].se.se);
add(node*2+1, tree[node].se.fi, tree[node].se.se);
tree[node].se={-1, -1};
}
add(node*2, tree[node].fi.fi, tree[node].fi.se);
add(node*2+1, tree[node].fi.fi, tree[node].fi.se);
tree[node].fi={-1, -1};
return;
}
void update(int node, int l, int r, int ql, int qr, int h, bool op) {
propagate(node, l, r);
if (l>qr || r<ql) return;
if (ql<=l && r<=qr) {
add(node, h, op);
return;
}
int mid=(l+r)/2;
update(node*2, l, mid, ql, qr, h, op);
update(node*2+1, mid+1, r, ql, qr, h, op);
}
vector<int> ans;
void query(int node, int l, int r) {
propagate(node, l, r);
if (l==r) {
if (tree[node].fi.se==-1) {
ans[l]=0;
return;
}
int res=0;
if (tree[node].fi.se==0) res=tree[node].fi.fi;
else if (tree[node].se.se!=-1) res=min(tree[node].se.fi, tree[node].fi.fi);
ans[l]=res;
return;
}
int mid=(l+r)/2;
query(node*2, l, mid);
query(node*2+1, mid+1, r);
}
vector<int> calc() {
ans.resize(n);
query(1, 0, n-1);
return ans;
}
};
void buildWall(int n, int k, int ops[], int left[], int right[], int height[], int finalHeight[]) {
SegTree st(n);
for (int i=0; i<k; i++) st.update(1, 0, n-1, left[i], right[i], height[i], ops[i]-1);
vector<int> ans=st.calc();
for (int i=0; i<n; i++) finalHeight[i]=ans[i];
return;
}
