#include <bits/stdc++.h>
using namespace std;
#define ll int
#define vl vector<ll>
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
ff(i, 0, n){
finalHeight[i] = 0;
}
vector<vl> ad(n+1), re(n+1);
ff(i, 0, k){
if(op[i] == 1){
ad[left[i]].pb(i);
re[right[i]+1].pb(i);
}
}
set<pll> calc;
calc.insert({0, -1});
ff(i, 0, n){
ff(j, 0, ad[i].size()){
calc.insert({height[ad[i][j]], ad[i][j]});
}
ff(j, 0, re[i].size()){
calc.erase({height[re[i][j]], re[i][j]});
}
auto x = calc.end();
x--;
finalHeight[i] = x->fi;
}
ad = vector<vl>(n+1);
re = vector<vl>(n+1);
ff(i, 0, k){
if(op[i] == 2){
ad[left[i]].pb(i);
re[right[i]+1].pb(i);
}
}
calc.clear();
calc.insert({1e9, -1});
ff(i, 0, n){
ff(j, 0, ad[i].size()){
calc.insert({height[ad[i][j]], ad[i][j]});
}
ff(j, 0, re[i].size()){
calc.erase({height[re[i][j]], re[i][j]});
}
auto x = calc.begin();
finalHeight[i] = min(finalHeight[i], x->fi);
}
/*ff(i, 0, n){
cout << finalHeight[i] << " ";
}*/
}
/*
int main(){
ll n, k;
cin >> n >> k;
ll a[n], b[n], c[n], d[n];
ff(i, 0, k){
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
ll x[n];
buildWall(n, k, a, b, c, d, x);
}
*/
