#include <bits/stdc++.h>
#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9
using namespace std;
int N;
vector<pii> tree;
vector<pii> lazy;
void relax(int node, int l, int r){
if(lazy[node].first == -oo && lazy[node].second == oo) return;
tree[node].first = max(lazy[node].first, tree[node].first);
tree[node].second = min(tree[node].second, lazy[node].second);
if(l != r){
lazy[node * 2 + 1].first = max(lazy[node * 2 + 1].first, lazy[node].first);
lazy[node * 2 + 2].second = min(lazy[node * 2 + 2].second, lazy[node].second);
}
lazy[node] = {-oo, oo};
}
void update(int node, int l, int r, int ul, int ur, pii val){
relax(node, l, r);
if(ur < l || r < ul){ return; }
if(ul <= l && r <= ur){
lazy[node] = val;
relax(node, l, r);
return;
}
int mid = (l + r) / 2;
update(node * 2 + 1, l, mid, ul, ur, val);
update(node * 2 + 2, mid + 1, r, ul, ur, val);
tree[node].first = min(tree[node * 2 + 1].first, tree[node * 2 + 2].first);
tree[node].second = max(tree[node * 2 + 1].second, tree[node * 2 + 2].second);
}
void ask(int node, int l, int r, int pos, int &ans){
relax(node, l, r);
if(l == r && r == pos){
ans = min(max(tree[node].first, ans), tree[node].second);
return;
}
int mid = (l + r) / 2;
if(pos <= mid){
ask(node * 2 + 1, l, mid, pos, ans);
}
else{
ask(node * 2 + 2, mid + 1, r, pos, ans);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = n;
tree.resize(N * 4, {0, oo});
lazy.resize(N * 4, {-oo, oo});
for (int i = 0; i < k; i++)
{
update(0, 0, n - 1, left[i], right[i], {height[i] * (op[i] == 1), height[i] * (op[i] == 2)});
}
for (int i = 0; i < n; i++)
{
ask(0, 0, n - 1, i, finalHeight[i]);
}
}
