// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
const int maxn = 2e6 + 5;
const int inf = 1e5;
struct D{
int mn, mx;
D(){
mn = 0;
mx = inf;
}
} node[maxn * 4];
int n, k, ans[maxn];
void change(int id, D d){
if(d.mn >= node[id].mx) node[id].mn = node[id].mx = d.mn;
else if(d.mx <= node[id].mn) node[id].mn = node[id].mx = d.mx;
else{
smax(node[id].mn, d.mn);
smin(node[id].mx, d.mx);
}
}
void relax(int id){
change(id * 2, node[id]);
change(id * 2 + 1, node[id]);
node[id].mn = 0;
node[id].mx = inf;
}
void upd(int s, int e, int ty, int h, int l = 0, int r = n, int id = 1){
if(s <= l && r <= e){
if(ty == 1){
if(h >= node[id].mx) node[id].mn = node[id].mx = h;
else smax(node[id].mn, h);
}
else{
if(h <= node[id].mn) node[id].mn = node[id].mx = h;
else smin(node[id].mx, h);
}
return;
}
if(e <= l || r <= s) return;
relax(id);
int mid = (l + r) / 2;
upd(s, e, ty, h, l, mid, id * 2);
upd(s, e, ty, h, mid, r, id * 2 + 1);
}
void get(int l = 0, int r = n, int id = 1){
if(l == r - 1){
ans[l] = node[id].mn;
return;
}
relax(id);
int mid = (l + r) / 2;
get(l, mid, id * 2);
get(mid, r, id * 2 + 1);
}
// int32_t main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// cin >> n >> k;
// while(k--){
// int l, r, ty, h; cin >> ty >> l >> r >> h;
// r++;
// upd(l, r, ty, h);
// }
// get();
// for(int i = 0; i < n; i++) cout << ans[i] << ' ';
// return 0;
// }
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
k = K;
for(int i = 0; i < k; i++) upd(left[i], right[i] + 1, op[i], height[i]);
get();
for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
}
