/** - dwuy -
／＞ フ
| _ _|
／`ミ _x ノ
/ |
/ ヽ ?
／￣| | | |
| (￣ヽ＿_ヽ_)_)
＼二つ
**/
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
using namespace std;
typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;
const long long OO = 2e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
struct SMT{
int n;
vector<pii> tree;
SMT(int n = 0) : n(n), tree(n<<2|3, {0, OO}) {}
pii combine(pii a, pii b){ /// a -> b;
a.fi = max(a.fi, b.fi);
a.se = max(a.se, a.fi);
a.se = min(a.se, b.se);
a.fi = min(a.fi, a.se);
return a;
}
void down(int id){
int ID = id<<1;
tree[ID] = combine(tree[ID], tree[id]);
tree[ID|1] = combine(tree[ID|1], tree[id]);
tree[id] = {0, OO};
}
void update(int l, int r, int id, const int &u, const int v, const pii &rv){
if(l > v || r < u) return;
if(l >= u && r <= v){
tree[id] = combine(tree[id], rv);
return;
}
down(id);
int mid = (l + r)>>1;
update(l, mid, id<<1, u, v, rv);
update(mid + 1, r, id<<1|1, u, v, rv);
}
void update(int u, int v, pii rv){
update(1, n, 1, u, v, rv);
}
int get(int pos){
int id = 1;
for(int lo=1, hi=n; lo<hi;){
int mid = (lo + hi)>>1;
down(id);
if(pos <= mid) hi = mid, id = id<<1;
else lo = mid + 1, id = id<<1|1;
}
return tree[id].fi;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int res[]){
SMT smt(n);
for(int i=0; i<k; i++){
if(op[i] == 1) smt.update(left[i] + 1, right[i] + 1, {height[i], INF});
else smt.update(left[i] + 1, right[i] + 1, {-INF, height[i]});
}
for(int i=1; i<=n; i++) res[i-1] = smt.get(i);
}
