#include <bits/stdc++.h>
#define vl first
#define vr second
//#include "wall.h"
using namespace std;
typedef pair<int,int> pii;
const int MN = 2e6+5;
pii ST[4*MN];
int finH[MN];
void init(int s, int e, int pos)
{
ST[pos].vl = 0;
ST[pos].vr = MN;
if(s==e) return;
int m = (s+e)/2;
init(s,m,2*pos);
init(m+1,e,2*pos+1);
}
void fin(int s, int e, int pos)
{
int L = ST[pos].vl, R = ST[pos].vr;
if(s==e){
finH[s] = L;
return;
}
int m = (s+e)/2;
ST[2*pos].vl = max(ST[2*pos].vl,L);
ST[2*pos].vr = max(ST[2*pos].vr,L);
ST[2*pos].vl = min(ST[2*pos].vl,R);
ST[2*pos].vr = min(ST[2*pos].vr,R);
ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
fin(s, m, 2*pos);
fin(m+1, e, 2*pos+1);
}
void upt(int qu, int l, int r, int h, int s, int e, int pos)
{
if(e<l || s>r) return;
int L = ST[pos].vl, R = ST[pos].vr;
if(l<=s && e<=r){
if(qu==1){
ST[pos].vl = max(L,h);
ST[pos].vr = max(R,h);
}
else{
ST[pos].vl = min(L,h);
ST[pos].vr = min(R,h);
}
return ;
}
int m = (s+e)/2;
ST[2*pos].vl = max(ST[2*pos].vl,L);
ST[2*pos].vr = max(ST[2*pos].vr,L);
ST[2*pos].vl = min(ST[2*pos].vl,R);
ST[2*pos].vr = min(ST[2*pos].vr,R);
ST[2*pos+1].vl = max(ST[2*pos+1].vl,L);
ST[2*pos+1].vr = max(ST[2*pos+1].vr,L);
ST[2*pos+1].vl = min(ST[2*pos+1].vl,R);
ST[2*pos+1].vr = min(ST[2*pos+1].vr,R);
ST[pos].vl = 0;
ST[pos].vr = MN;
upt(qu, l, r, h, s, m, 2*pos);
upt(qu, l, r, h, m+1, e, 2*pos+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
init(0,n-1,1);
//cout << height[0] << '\n';
for(int i=0; i<k; i++) upt(op[i],left[i],right[i],height[i],0,n-1,1);
//cout << 1 << '\n';
fin(0,n-1,1);
for(int i=0; i<n; i++) finalHeight[i] = finH[i];
};
