#include "wall.h"
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
struct node{
ll mn=0,mx=0;
ll lmn=INF,lmx=-INF;
};
const int MAXN = 2e6;
vector<node>t;
void mxx(node &a,node &b){
b.mx = max(b.mx,a.lmx);
b.mn = max(b.mn,a.lmx);
b.lmx = max(b.lmx,a.lmx);
a.lmx = -INF;
b.lmn = INF;
}
void mnn(node &a,node &b){
b.mx = min(b.mx,a.lmn);
b.mn = min(b.mn,a.lmn);
b.lmn = min(b.lmn,a.lmn);
a.lmn = INF;
b.lmx = -INF;
}
void pushdown(int v){
if(t[v].lmx != -INF){
ll tmp = t[v].lmx;
mxx(t[v],t[2*v]);
t[v].lmx = tmp;
mxx(t[v],t[2*v+1]);
}else if(t[v].lmn != INF){
ll tmp = t[v].lmn;
mnn(t[v],t[2*v]);
t[v].lmn = tmp;
mnn(t[v],t[2*v+1]);
}
}
vector<ll>ans;
void upd(int v,int l,int r,int tl,int tr,int mode,ll val){
if(l > r)return;
pushdown(v);
if(l == tl && r == tr){
if(mode){
t[v].mx = max(t[v].mx,val);
t[v].mn = max(t[v].mn,val);
t[v].lmx = max(t[v].lmx,val);
}else{
t[v].mx = min(t[v].mx,val);
t[v].mn = min(t[v].mn,val);
t[v].lmn = min(t[v].lmn,val);
}
return;
}
int tm = (tl+tr)/2;
upd(2*v,l,min(r,tm),tl,tm,mode,val);
upd(2*v+1,max(l,tm+1),r,tm+1,tr,mode,val);
t[v].mx = max(t[2*v].mx,t[2*v+1].mx);
t[v].mn = min(t[2*v].mn,t[2*v+1].mn);
}
void query(int v,int l,int r){
if(l == r){
ans[l] = t[v].mx;
return;
}
pushdown(v);
int tm = (l+r)/2;
query(2*v,l,tm);
query(2*v+1,tm+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
t.resize(8*(n+1));
ans.resize(n+1);
for(int i=0;i<k;i++){
left[i]++;
right[i]++;
upd(1,left[i],right[i],1,n,op[i]%2,height[i]);
}
query(1,1,n);
for(int i=0;i<n;i++){
finalHeight[i] = ans[i+1];
}
}
/*
int main()
{
int n,k;
cin>>n>>k;
while(k--){
int t,l,r,x;
cin>>t>>l>>r>>x;
l++;r++;
upd(1,l,r,1,n,t%2,x);
cout<<"upd"<<'\n';
query(1,1,n);
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<'\n';
}
}
*/
