#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define name "wall"
#define MAXN 2000006
#define pb push_back
#define pf push_front
#define ll long long
#define ii pair<int, int>
#define fs first
#define sc second
#define ill pair<int, ll>
#define lli pair<ll, int>
#define llll pair<ll, ll>
#define all(v) v.begin(),v.end()
#define uni(v) v.erase(unique(all(v)),v.end())
#define bit(n,i) (((n)>>(i))&1)
#define FOR(i,a,b) for (int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for (int i=(a),_b=(b); i>=_b; i--)
#define MASK(i) (1LL<<(i))
const int INF=1e9;
const int MOD=1e9+7;
void add(int &u, int v){
u+=v;
if (u>=MOD) u-=MOD;
}
void sub(int &u, int v){
u-=v;
if (u<0) u+=MOD;
}
bool minimize(int &u, int v){
if (u>v){
u=v;
return 1;
}
return 0;
}
bool maximize(int &u, int v){
if (u<v){
u=v;
return 1;
}
return 0;
}
long long Rand(long long l, long long r){
ll tmp=0;
FOR(i,1,4) tmp=((tmp<<15)^(((1<<15)-1)&rand()));
return l+tmp%(r-l+1);
}
int Max[4*MAXN],Min[4*MAXN];
int lazy[4*MAXN];
void down(int id, int l, int r){
if (l==r||lazy[id]==INF) return;
Max[id<<1]=Max[id<<1|1]=lazy[id];
Min[id<<1]=Min[id<<1|1]=lazy[id];
lazy[id<<1]=lazy[id<<1|1]=lazy[id];
lazy[id]=INF;
}
void update_max(int id, int l, int r, int u, int v, int val, int times){
if (l>v||r<u||Min[id]>=val) return;
if (l>=u&&r<=v&&Max[id]<val){
Max[id]=Min[id]=val;
lazy[id]=val;
down(id,l,r);
return;
}
down(id,l,r);
int mid=(l+r)/2;
update_max(id<<1,l,mid,u,v,val,times);
update_max(id<<1|1,mid+1,r,u,v,val,times);
Max[id]=max(Max[id<<1],Max[id<<1|1]);
Min[id]=min(Min[id<<1],Min[id<<1|1]);
}
void update_min(int id, int l, int r, int u, int v, int val, int times){
if (l>v||r<u||Max[id]<=val) return;
if (l>=u&&r<=v&&Min[id]>val){
Max[id]=Min[id]=val;
lazy[id]=val;
down(id,l,r);
return;
}
down(id,l,r);
int mid=(l+r)/2;
update_min(id<<1,l,mid,u,v,val,times);
update_min(id<<1|1,mid+1,r,u,v,val,times);
Max[id]=max(Max[id<<1],Max[id<<1|1]);
Min[id]=min(Min[id<<1],Min[id<<1|1]);
}
void get(int id, int l, int r, int res[]){
if (l==r){
res[l-1]=Max[id];
return;
}
down(id,l,r);
int mid=(l+r)/2;
get(id<<1,l,mid,res);
get(id<<1|1,mid+1,r,res);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int finalHeight[]){
FOR(id,1,4*n) lazy[id]=INF;
FORD(i,q,1){
op[i]=op[i-1];
l[i]=l[i-1]+1;
r[i]=r[i-1]+1;
h[i]=h[i-1];
}
FOR(i,1,q){
int type=op[i],u=l[i],v=r[i],val=h[i];
if (type==1) update_max(1,1,n,u,v,val,i);
else update_min(1,1,n,u,v,val,i);
}
get(1,1,n,finalHeight);
}
