#include "wall.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pii pair<int, int>
#define ld long double
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e9 + 9;
const int MAX = 2e6 + 6;
int MOD = 998244353;
array<int, 2> lazy[4 * MAX];
int ans[MAX];
void add(array<int, 2> &a, array<int, 2> b){
if(a[1] < b[0]) a = {b[0], b[0]};
else if(b[1] < a[0]) a = {b[1], b[1]};
else a = {max(a[0], b[0]), min(a[1], b[1])};
}
void relax(int node){
add(lazy[2 * node], lazy[node]);
add(lazy[2 * node + 1], lazy[node]);
lazy[node] = {0, oo};
}
void update(int node, int l, int r, int ul, int ur, int ty, int val){
if(ur < l || r < ul) return;
if(l != r) relax(node);
if(ul <= l && r <= ur){
if(l != r) relax(node);
if(ty == 1) add(lazy[node], {val, oo});
else add(lazy[node], {0, val});
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ul, ur, ty, val);
update(2 * node + 1, mid + 1, r, ul, ur, ty, val);
}
void build(int node, int l, int r){
if(l == r){
ans[l] = lazy[node][0];
return;
}
relax(node);
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i <= 4 * n; i++) lazy[i] = {0, oo};
for(int i = 0; i < k; i++){
update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
build(1, 0, n - 1);
for(int i = 0; i < n; i++){
finalHeight[i] = ans[i];
}
}
