#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define lpos pos<<1
#define rpos pos<<1|1
const int SIZE = 2e6 + 5;
const int INF = (1ll << 31) - 1;
int mx[3 * SIZE], mn[3 * SIZE];
void add (int pos, int x) {
if (mx[pos] == -1)
mn[pos] = max (mn[pos], x);
else if (x >= mx[pos])
mn[pos] = x, mx[pos] = -1;
else if (x >= mn[pos])
mn[pos] = x;
}
void del (int pos, int x) {
if (mx[pos] == -1)
mn[pos] = min (mn[pos], x);
else if (x <= mn[pos])
mn[pos] = x, mx[pos] = -1;
else if (x <= mx[pos])
mx[pos] = x;
}
void push_down (int pos) {
if (mx[pos] == -1) {
mx[lpos] = mx[rpos] = -1;
mn[lpos] = mn[rpos] = mn[pos];
mx[pos] = INF, mn[pos] = 0;
} else {
if (mn[pos] != 0) {
add (lpos, mn[pos]);
add (rpos, mn[pos]);
}
if (mx[pos] != INF) {
del (lpos, mx[pos]);
del (rpos, mx[pos]);
}
mx[pos] = INF, mn[pos] = 0;
}
}
void modify (int pos, int l, int r, int L, int R, int t, int h) {
if (l == L && r == R) {
if (t == 1)
add (pos, h);
else
del (pos, h);
} else {
push_down (pos);
int mid = (L + R) / 2;
if (r <= mid)
modify (lpos, l, r, L, mid, t, h);
else if (l > mid)
modify (rpos, l, r, mid + 1, R, t, h);
else {
modify (lpos, l, mid, L, mid, t, h);
modify (rpos, mid + 1, r, mid + 1, R, t, h);
}
}
}
void dfs (int pos, int l, int r, int ans[]) {
if (l == r)
ans[l] = mn[pos];
else {
push_down (pos);
int mid = (l + r) / 2;
dfs (lpos, l, mid, ans);
dfs (rpos, mid + 1, r, ans);
}
}
void buildWall (int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
fill (mx, mx + 3 * n + 1, INF);
fill (mn, mn + 3 * n + 1, 0);
for (int i = 0; i < k; i++)
modify (1, l[i], r[i], 0, n - 1, op[i], h[i]);
dfs (1, 0, n - 1, ans);
}
