#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxN = 2 * 1e5;
struct node
{
int min, max, add, destruct;
};
struct segmentTree
{
int size;
vector<node> val;
void build(int n, int index, int Lx, int Rx)
{
if(Rx - Lx == 1)
{
if(Lx < n)
{
val[index] = {0, 0, -1, -1};
}
else
{
val[index] = {INT_MAX, -INT_MAX, -1, -1};
}
}
else
{
int m = (Lx + Rx) / 2;
build(n, index * 2 + 1, Lx, m);
build(n, index * 2 + 2, m, Rx);
val[index] = {0, 0, -1, -1};
}
}
void build(int n)
{
size = 1;
while(size < n) size <<= 1;
val = vector<node>(size * 2);
build(n, 0, 0, size);
}
void add(int index, int h)
{
val[index].min = max(val[index].add, h);
val[index].add = val[index].min;
val[index].max = max(val[index].max, val[index].min);
if(val[index].destruct != -1)
{
val[index].destruct = max(val[index].destruct, val[index].add);
}
}
void destruct(int index, int h)
{
if(val[index].destruct != -1)
{
val[index].max = min(val[index].destruct, h);
}
else
{
val[index].max = h;
}
val[index].destruct = val[index].max;
val[index].min = min(val[index].min, val[index].max);
if(val[index].add != -1)
{
val[index].add = min(val[index].add, val[index].destruct);
}
}
node func(node left, node right)
{
return {min(left.min, right.min), max(left.max, right.max), -1, -1};
}
void add(int l, int r, int h, int index, int Lx, int Rx)
{
if(Rx <= l || Lx >= r) return;
if(Lx >= l && Rx <= r)
{
add(index, h);
return;
}
if(val[index].add != -1)
{
add(index * 2 + 1, val[index].add);
add(index * 2 + 2, val[index].add);
val[index].add = -1;
}
if(val[index].destruct != -1)
{
destruct(index * 2 + 1, val[index].destruct);
destruct(index * 2 + 2, val[index].destruct);
val[index].destruct = -1;
}
int m = (Rx + Lx) / 2;
add(l, r, h, index * 2 + 1, Lx, m);
add(l, r, h, index * 2 + 2, m, Rx);
val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
}
void add(int l, int r, int h)
{
add(l, r, h, 0, 0, size);
}
void destruct(int l, int r, int h, int index, int Lx, int Rx)
{
if(Rx <= l || Lx >= r) return;
if(Lx >= l && Rx <= r)
{
destruct(index, h);
return;
}
if(val[index].destruct != -1)
{
destruct(index * 2 + 1, val[index].destruct);
destruct(index * 2 + 2, val[index].destruct);
val[index].destruct = -1;
}
if(val[index].add != -1)
{
add(index * 2 + 1, val[index].add);
add(index * 2 + 2, val[index].add);
val[index].add = -1;
}
int m = (Rx + Lx) / 2;
destruct(l, r, h, index * 2 + 1, Lx, m);
destruct(l, r, h, index * 2 + 2, m, Rx);
val[index] = func(val[index * 2 + 1], val[index * 2 + 2]);
}
void destruct(int l, int r, int h)
{
destruct(l, r, h, 0, 0, size);
}
vector<int> ans;
void print(int n, int index, int Lx, int Rx)
{
if(Rx - Lx == 1)
{
if(Lx < n)
{
ans.push_back(val[index].min);
}
return;
}
if(val[index].add != -1)
{
add(index * 2 + 1, val[index].add);
add(index * 2 + 2, val[index].add);
val[index].add = -1;
}
if(val[index].destruct != -1)
{
destruct(index * 2 + 1, val[index].destruct);
destruct(index * 2 + 2, val[index].destruct);
val[index].destruct = -1;
}
if(val[index].min == val[index].max && val[index].min != -1)
{
for(int i = 0; i < Rx - Lx; i++)
{
if(Lx + i < n)
{
ans.push_back(val[index].min);
}
else
{
break;
}
}
return;
}
int m = (Rx + Lx) / 2;
print(n, index * 2 + 1, Lx, m);
print(n, index * 2 + 2, m, Rx);
}
void print(int n)
{
print(n, 0, 0, size);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segmentTree st;
st.build(n);
for(int i=0; i<k; i++)
{
int o=op[i], l=left[i], r=right[i], h=height[i];
r++;
if(o == 1)
{
st.add(l, r, h);
}
else
{
st.destruct(l, r, h);
}
}
st.print(n);
for(int i=0; i<n; i++) finalHeight[i]=st.ans[i];
}
