#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
int lazy[8000005][2][2];
int n;
void build(){
for(int i=1; i<2*n; i++){
lazy[i][0][0]=1e9;
lazy[i][1][0]=0;
lazy[i][0][1]=0;
lazy[i][1][1]=0;
}
}
void setmax(int l, int r, int range_l, int range_r, int val, int pri){
if (l>range_r || r<range_l)return;
if (l>=range_l && r<=range_r){
int x = l+n, y=r+n;
while(x!=y){x>>=1; y>>=1;}
lazy[x][1][0] = max(val, lazy[x][1][0]);
lazy[x][1][1] = pri;
return;
}
int mid = (l+r)/2;
setmax(l, mid, range_l, range_r, val, pri);
setmax(mid+1, r, range_l, range_r, val, pri);
}
void setmin(int l, int r, int range_l, int range_r, int val, int pri){
if (l>range_r || r<range_l)return;
if (l>=range_l && r<=range_r){
int x = l+n, y=r+n;
while(x!=y){x>>=1; y>>=1;}
lazy[x][0][0] = min(val, lazy[x][0][0]);
lazy[x][0][1] = pri;
return;
}
int mid = (l+r)/2;
setmin(l, mid, range_l, range_r, val, pri);
setmin(mid+1, r, range_l, range_r, val, pri);
}
int n_now;
void solve(int ans[]){
for(int i=0; i<n_now; i++){
ans[i]=0;
vector<vector<int>> op;
for(int x=i+n; x>0; x>>=1){
if(lazy[x][1][1]>0) op.push_back({lazy[x][1][1], 1, lazy[x][1][0]});
if(lazy[x][0][1]>0) op.push_back({lazy[x][0][1], 2, lazy[x][0][0]});
}
sort(op.begin(), op.end(), [](vector<int> a, vector<int> b){return a[0]<b[0];});
for(vector<int> o: op){
if(o[1]==1) ans[i]=max(ans[i], o[2]);
else ans[i]=min(ans[i], o[2]);
}
}
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalheight[]){
n_now=N;
n = pow(2, ceil(log2(N)));
build();
for(int i=0; i<k; i++){
if(op[i] == 1){
setmax(0, n-1, left[i], right[i], height[i], i+1);
}
else{
setmin(0, n-1, left[i], right[i], height[i], i+1);
}
}
solve(finalheight);
}
