#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> ans;
const int mxn = 2e6;
const long long inf = 1e18;
long long sg[4*mxn+5],mn[4*mxn+5],mx[4*mxn+5],lz[4*mxn+5];
void build(int nd, int l, int r){
int md = (l+r)>>1;
if(l == r){
sg[nd] = -inf;
return;
}
sg[nd] = -inf;
build(2*nd, l, md), build(2*nd+1, md+1, r);
}
void pro(int nd, int l, int r){
mx[nd] = mn[nd] = sg[nd];
if(l < r){
sg[2*nd] = sg[2*nd+1] = sg[nd];
}
sg[nd] = -inf;
}
void bagi(int nd, int l, int r){
mx[nd] = max(mx[2*nd+1], mx[2*nd]);
mn[nd] = min(mn[2*nd+1], mn[2*nd]);
return;
}
void upd(int nd, int l, int r, int lf, int rg, int v, int op){
if(op&1){
if(sg[nd] != -inf) pro(nd, l, r);
if(l > rg || r < lf || mn[nd] >= v) return;
if(lf <= l && r <= rg && mn[nd] == mx[nd]){
sg[nd] = v; pro(nd,l,r);
return;
}
int md = (l+r)>>1;
upd(2*nd, l, md, lf, rg, v, op);
upd(2*nd+1, md+1, r, lf, rg, v, op);
bagi(nd, l, r);
}else{
if(sg[nd] != -inf) pro(nd, l, r);
if(l > rg || r < lf || mx[nd] <= v) return;
if(lf <= l && r <= rg && mn[nd] == mx[nd]){
sg[nd] = v; pro(nd,l,r);
return;
}
int md = (l+r)>>1;
upd(2*nd, l, md, lf, rg, v, op);
upd(2*nd+1, md+1, r, lf, rg, v, op);
bagi(nd, l, r);
}
}
void jawab(int nd, int l, int r){
if(sg[nd] != -inf) pro(nd,l,r);
int md = (l+r)>>1;
if(mx[nd] == mn[nd]){
for(int i = l; i <= r; i++) ans[i] = mx[nd];
return;
}
jawab(2*nd,l,md);
jawab(2*nd+1,md+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
ans = vector<long long>(n+1, 0);
build(1,0,n-1);
for(int i = 0; i < k; i++){
if(op[i]&1){
upd(1,0,n-1,left[i],right[i],height[i],op[i]);
}else{
upd(1,0,n-1,left[i],right[i],height[i],op[i]);
}
}
jawab(1,0,n-1);
for(int i = 0; i < n; i++)finalHeight[i] = ans[i];
return;
}
/*
int main(){
int n,k; cin >> n >> k;
int op[k],left[k],right[k],height[k],finalheight[n];
for(int i = 0; i < k; i++) cin >> op[i] >> left[i] >> right[i] >> height[i];
buildWall(n,k,op,left,right,height,finalheight);
for(int i = 0; i < n; i++) cout << ans[i] << ' ';
}*/
