#include "wall.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
class Lazy_Segment_Tree{
private:
int n;
vp date;
int f(int x,P p){
if(x<p.first) return p.first;
if(p.second<x) return p.second;
return x;
}
void Set_Lazy(int k,P p){
date[k]={f(date[k].first,p),f(date[k].second,p)};
}
void Push(int k){
Set_Lazy(k*2+1,date[k]);
Set_Lazy(k*2+2,date[k]);
date[k]={-inf,inf};
}
void Rec(int a,int b,int k,int l,int r,P p){
if(r<=a||b<=l) return;
if(a<=l&&r<=b){
Set_Lazy(k,p);
return;
}
Push(k);
int m=(l+r)/2;
Rec(a,b,k*2+1,l,m,p);
Rec(a,b,k*2+2,m,r,p);
}
public:
Lazy_Segment_Tree(int n_){
n=1;
while(n<n_) n*=2;
date=vp(2*n-1,{-inf,inf});
}
void Query(int a,int b,P p){
return Rec(a,b,0,0,n,p);
}
vi Open(){
vi a(n);
for(int i=0;i<n-1;i++) Push(i);
for(int i=0;i<n;i++) a[i]=f(0,date[i+n-1]);
return a;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
Lazy_Segment_Tree st(n);
for(int i=0;i<k;i++){
if(op[i]==1) st.Query(left[i],right[i]+1,{height[i],inf});
else st.Query(left[i],right[i]+1,{-inf,height[i]});
}
vi a=st.Open();
for(int i=0;i<n;i++) finalHeight[i]=a[i];
}
