#include<wall.h>
#include<bits/stdc++.h>
using namespace std;
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<int> > add1;
vector<vector<int> >add2;
vector<vector<int> > sub1;
vector<vector<int> > sub2;
for(int i=0; i<k; i++){
if(op[i]==1){
add1[left[i]].push_back(hight[i]);
add2[right[i]].push_back(hight[i]);
}
else{
sub1[left[i]].push_back(hight[i]);
sub2[left[i]].push_back(hight[i]);
}
}
multiset<int> active;
for(int i=0; i<n; i++){
for(auto e: add1[i]){
active.insert(e);
}
int h=*prev(active.end());
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=*active.begin();
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<=1e4){
buildWallsmall(n, k, op, left, right, hight, finalHight);
}
buildWall2(n, k, op, left, right, hight, finalHight);
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}*/
