#include<wall.h>
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
void buildWallsmall(int n, int k, signed op[], signed left[], signed right[],
signed hight[], signed finalHight[]){
for(int i=0; i<k; i++){
for(int j=left[i]; j<=right[i]; j++){
if(op[i]==1){
finalHight[j]=max(finalHight[j], hight[i]);
}
else{
finalHight[j]=min(finalHight[j], hight[i]);
}
}
}
}
void buildWall2(int n, int k, signed op[], signed left[], signed right[],
signed hight[], signed finalHight[]){
vector<vector<pair<int,int> > > add1(n);
vector<vector<pair<int,int> > >add2(n);
vector<vector<pair<int,int> > > sub1(n);
vector<vector<pair<int,int> > > sub2(n);
for(int i=0; i<k; i++){
if(op[i]==1){
add1[left[i]].push_back({hight[i], i});
add2[right[i]].push_back({hight[i], i});
}
else{
sub1[left[i]].push_back({hight[i], i});
sub2[right[i]].push_back({hight[i], i});
}
}
set<pair<int,int> > active;
for(int i=0; i<n; i++){
for(auto e: add1[i]){
active.insert(e);
}
int h=0;
if(!active.empty()){
h=(*prev(active.end())).first;
}
finalHight[i]=h;
for(auto e: add2[i]){
active.erase(e);
}
}
active.clear();
for(int i=0; i<n; i++){
for(auto e: sub1[i]){
active.insert(e);
}
int h=inf;
if(!active.empty()){
h=(*active.begin()).first;
}
finalHight[i]=min(finalHight[i], h);
for(auto e: sub2[i]){
active.erase(e);
}
}
}
void buildWall(int n, int k, signed op[], signed left[], signed right[],
signed hight[], signed finalHight[]){
if(n<=(int)1e4){
buildWallsmall(n, k, op, left, right, hight, finalHight);
return;
}
buildWall2(n, k, op, left, right, hight, finalHight);
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}*/
