# include <bits/stdc++.h>
# define x first
# define y second
# define mp make_pair
// everything go according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1 Y_U_NO_y1
# define left Y_U_NO_left
# define right Y_U_NO_right
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef long double ld;
const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
const int N = 2e6 + 1;
struct segtree {
int n;
int mx[4*N], mn[4*N];
int add[4*N];
segtree (int n) : n(n) {
memset (add, -1, sizeof add);
}
void push (int v, int tl, int tr) {
if (add[v] < 0)
return;
if (tl != tr) {
add[2*v] = add[v];
add[2*v + 1] = add[v];
}
mn[v] = mx[v] = add[v];
add[v] = -1;
}
int l, r, h, tp;
void update (int a, int b, int c, int d) {
l = a,
r = b,
h = c,
tp = d;
update (1, 1, n);
}
void update (int v, int tl, int tr) {
push (v, tl, tr);
if (tr < l || tl > r)
return;
if ((tp == 1 && mn[v] >= h) || (tp == 2 && mx[v] < h))
return;
if (l <= tl && tr <= r && ((tp == 1 && mx[v] <= h) || (tp == 2 && mn[v] >= h))) {
add[v] = h;
push (v, tl, tr);
return;
}
int tmid = (tl+tr) >> 1;
update (2*v, tl, tmid);
update (2*v + 1, tmid+1, tr);
recalc (v);
}
void recalc (int v) {
mx[v] = max (mx[2*v], mx[2*v + 1]);
mn[v] = min (mn[2*v], mn[2*v + 1]);
}
void get (int v, int tl, int tr, int ans[]) {
push (v, tl, tr);
if (tl == tr) {
ans[tl - 1] = mn[v];
return;
}
int tmid = (tl+tr) >> 1;
get (2*v, tl, tmid, ans);
get (2*v + 1, tmid+1, tr, ans);
}
void get (int ans[]) {
get (1, 1, n, ans);
}
};
void buildWall (int n, int k, int tp[], int l[], int r[], int h[], int ans[]) {
segtree T (n);
for (int i = 0; i < k; i++) {
//break;
l[i]++, r[i]++;
T.update (l[i], r[i], h[i], tp[i]);
}
T.get (ans);
}
