#ifndef FEXT
#include "wall.h"
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;
struct toi_la_nguoi_trung_quoc{
struct segnode_t{
int mx, mx2, cntmx;
int mn, mn2, cntmn;
int lazymx, lazymn;
segnode_t(int x = 0){
mx = x; mx2 = INT_MIN; cntmx = 1;
mn = x; mn2 = INT_MAX; cntmn = 1;
lazymx = lazymn = -1;
}
friend segnode_t merge(const segnode_t &lhs, const segnode_t &rhs){
segnode_t cac;
cac.mx = max(lhs.mx, rhs.mx);
cac.mx2 = max(lhs.mx == cac.mx ? lhs.mx2 : lhs.mx, rhs.mx == cac.mx ? rhs.mx2 : rhs.mx);
cac.cntmx = (lhs.mx == cac.mx ? lhs.cntmx : 0) + (rhs.mx == cac.mx ? rhs.cntmx : 0);
cac.mn = min(lhs.mn, rhs.mn);
cac.mn2 = min(lhs.mn == cac.mn ? lhs.mn2 : lhs.mn, rhs.mn == cac.mn ? rhs.mn2 : rhs.mn);
cac.cntmn = (lhs.mn == cac.mn ? lhs.cntmn : 0) + (rhs.mn == cac.mn ? rhs.cntmn : 0);
cac.lazymx = cac.lazymn = -1;
return cac;
}
friend ostream& operator<< (ostream& out, const segnode_t &rhs){
out << '{';
out << rhs.mx << ' ' << rhs.mx2 << ' ' << rhs.cntmx << ' ' << rhs.mn << ' ' << rhs.mn2 << ' ' << rhs.cntmn << ' ' << rhs.lazymx << ' ' << rhs.lazymn;
out << '}';
return out;
}
};
segnode_t seg[1 << 22];
void build(int id, int l, int r){
if (l == r){
seg[id] = segnode_t(0);
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
}
void down(int id, bool debug = 0){
if (debug) cout << "down " << id << endl;
if (debug) cout << seg[id] << endl << seg[id * 2] << endl << seg[id * 2 + 1] << endl;
int mx = max(seg[id * 2].mx, seg[id * 2 + 1].mx);
int mn = min(seg[id * 2].mn, seg[id * 2 + 1].mn);
if (seg[id].lazymx != -1 and seg[id * 2].mx == mx){
seg[id * 2].mx = seg[id].lazymx;
seg[id * 2].lazymx = seg[id].lazymx;
if (seg[id * 2].mx2 == INT_MIN or seg[id * 2].mn2 == INT_MAX){
seg[id * 2].mn = seg[id].lazymx;
seg[id * 2].lazymn = seg[id].lazymx;
}
}
if (seg[id].lazymn != -1 and seg[id * 2].mn == mn){
seg[id * 2].mn = seg[id].lazymn;
seg[id * 2].lazymn = seg[id].lazymn;
if (seg[id * 2].mx2 == INT_MIN or seg[id * 2].mn2 == INT_MAX){
seg[id * 2].mx = seg[id].lazymn;
seg[id * 2].lazymx = seg[id].lazymn;
}
}
if (seg[id * 2].mn != seg[id * 2].mx){
seg[id * 2].mn2 = min(seg[id * 2].mn2, seg[id * 2].mx);
seg[id * 2].mx2 = max(seg[id * 2].mx2, seg[id * 2].mn);
}
if (seg[id].lazymx != -1 and seg[id * 2 + 1].mx == mx){
seg[id * 2 + 1].mx = seg[id].lazymx;
seg[id * 2 + 1].lazymx = seg[id].lazymx;
if (seg[id * 2 + 1].mx2 == INT_MIN or seg[id * 2 + 1].mn2 == INT_MAX){
seg[id * 2 + 1].mn = seg[id].lazymx;
seg[id * 2 + 1].lazymn = seg[id].lazymx;
}
}
if (seg[id].lazymn != -1 and seg[id * 2 + 1].mn == mn){
seg[id * 2 + 1].mn = seg[id].lazymn;
seg[id * 2 + 1].lazymn = seg[id].lazymn;
if (seg[id * 2 + 1].mx2 == INT_MIN or seg[id * 2 + 1].mn2 == INT_MAX){
seg[id * 2 + 1].mx = seg[id].lazymn;
seg[id * 2 + 1].lazymx = seg[id].lazymn;
}
}
if (seg[id * 2 + 1].mn != seg[id * 2 + 1].mx){
seg[id * 2 + 1].mn2 = min(seg[id * 2 + 1].mn2, seg[id * 2 + 1].mx);
seg[id * 2 + 1].mx2 = max(seg[id * 2 + 1].mx2, seg[id * 2 + 1].mn);
}
seg[id].lazymx = seg[id].lazymn = -1;
if (debug) cout << seg[id] << endl << seg[id * 2] << endl << seg[id * 2 + 1] << endl;
}
void update_smax(int id, int l, int r, int u, int v, int x, bool debug = 0, bool debugdown = 0){
if (v < l or r < u or seg[id].mn >= x){
return;
}
if (debug) cout << "update_smax " << id << ' ' << l << ' ' << r << ' ' << u << ' ' << v << ' ' << x << endl;
if (debug) cout << seg[id] << endl;
if (u <= l and r <= v and seg[id].mn2 > x){
seg[id].lazymn = x;
seg[id].mn = x;
if (seg[id].mn2 == INT_MAX){
seg[id].lazymx = x;
seg[id].mx = x;
}
if (seg[id].mn != seg[id].mx){
seg[id].mn2 = min(seg[id].mn2, seg[id].mx);
seg[id].mx2 = max(seg[id].mx2, seg[id].mn);
}
if (debug) cout << "update_smax assign " << id << ' ' << seg[id] << endl;
return;
}
down(id, debugdown);
int mid = (l + r) >> 1;
update_smax(id * 2, l, mid, u, v, x, debug, debugdown);
update_smax(id * 2 + 1, mid + 1, r, u, v, x, debug, debugdown);
seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
if (debug) cout << "update_smax merge " << id << ' ' << seg[id] << endl;
}
void update_smin(int id, int l, int r, int u, int v, int x, bool debug = 0, bool debugdown = 0){
if (v < l or r < u or seg[id].mx <= x){
return;
}
if (debug) cout << "update_smin " << id << ' ' << l << ' ' << r << ' ' << u << ' ' << v << ' ' << x << endl;
if (debug) cout << seg[id] << endl;
if (u <= l and r <= v and seg[id].mx2 < x){
seg[id].lazymx = x;
seg[id].mx = x;
if (seg[id].mx2 == INT_MIN){
seg[id].lazymn = x;
seg[id].mn = x;
}
if (seg[id].mn != seg[id].mx){
seg[id].mn2 = min(seg[id].mn2, seg[id].mx);
seg[id].mx2 = max(seg[id].mx2, seg[id].mn);
}
if (debug) cout << "update_smin assign " << id << ' ' << seg[id] << endl;
return;
}
down(id, debugdown);
int mid = (l + r) >> 1;
update_smin(id * 2, l, mid, u, v, x, debug, debugdown);
update_smin(id * 2 + 1, mid + 1, r, u, v, x, debug, debugdown);
seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
if (debug) cout << "update_smin merge " << id << ' ' << seg[id] << endl;
}
int get(int id, int l, int r, int i, bool debug = 0, bool debugdown = 0){
if (l == r){
return seg[id].mx;
}
down(id, debugdown);
int mid = (l + r) >> 1;
if (i <= mid){
return get(id * 2, l, mid, i, debug, debugdown);
}
else{
return get(id * 2 + 1, mid + 1, r, i, debug, debugdown);
}
}
} seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
seg.build(1, 0, n - 1);
For(i, 0, k){
if (op[i] == 1){
seg.update_smax(1, 0, n - 1, left[i], right[i], height[i]);
}
else if (op[i] == 2){
seg.update_smin(1, 0, n - 1, left[i], right[i], height[i]);
}
// For(j, 0, n){
// cout << seg.get(1, 0, n - 1, j) << ' ';
// } cout << endl;
}
For(i, 0, n){
finalHeight[i] = seg.get(1, 0, n - 1, i);
}
return;
}
#ifdef FEXT
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("KEK.inp", "r", stdin);
freopen("KEK.out", "w", stdout);
int n, k; cin >> n >> k;
int op[k], left[k], right[k], height[k];
For(i, 0, k){
cin >> op[i] >> left[i] >> right[i] >> height[i];
}
int finalHeight[n];
buildWall(n, k, op, left, right, height, finalHeight);
For(i, 0, n){
cout << finalHeight[i] << ' ';
} cout << endl;
}
#endif
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
