// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
#define ll long long
const int BIG = 2e9 + 500;
struct segTree
{
struct Node
{
int mx = 0, mn = BIG, last = 0;
};
vector<Node> tree;
int sz;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz);
}
// 0 - min=
// 1 - max=
int C1, C2, C3;
void upd(int v, pii op)
{
if (tree[v].last == op.f)
{
if (op.f == 1)
tree[v].mx = max(tree[v].mx, op.s);
else
tree[v].mn = min(tree[v].mn, op.s);
}
else
{
if (op.f == 1)
{
C1 = tree[v].mx;
C2 = tree[v].mn;
C3 = op.s;
tree[v].mx = max(min(C1, C2), C3);
}
else
{
C1 = tree[v].mn;
C2 = tree[v].mx;
C3 = op.s;
tree[v].mn = min(max(C1, C2), C3);
}
tree[v].last = op.f;
}
}
void push(int v)
{
if (tree[v].last == 0)
{
if (tree[v].mx != 0)
{
upd(v * 2 + 1, {1, tree[v].mx});
upd(v * 2 + 2, {1, tree[v].mx});
}
if (tree[v].mn != BIG)
{
upd(v * 2 + 1, {0, tree[v].mn});
upd(v * 2 + 2, {0, tree[v].mn});
}
}
else
{
if (tree[v].mn != BIG)
{
upd(v * 2 + 1, {0, tree[v].mn});
upd(v * 2 + 2, {0, tree[v].mn});
}
if (tree[v].mx != 0)
{
upd(v * 2 + 1, {1, tree[v].mx});
upd(v * 2 + 2, {1, tree[v].mx});
}
}
tree[v].mx = 0;
tree[v].mn = BIG;
}
void addOp(int l, int r, pii &op, int v, int lv, int rv)
{
if (l <= lv and rv <= r)
{
upd(v, op);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
push(v);
addOp(l, r, op, v * 2 + 1, lv, m);
addOp(l, r, op, v * 2 + 2, m, rv);
}
void addOp(int l, int r, pii op)
{
addOp(l, r, op, 0, 0, sz);
}
void outArray(vector<int> &a, int v, int lv, int rv)
{
if (rv - lv == 1)
{
if (lv < a.size())
{
// while (tree[v].ops.size())
// {
// pii op = tree[v].ops.front();
// tree[v].ops.pop_front();
// a[lv] = op.f ? max(a[lv], op.s) : min(a[lv], op.s);
// }
if (tree[v].last == 0)
{
// cout << lv << " " << tree[v].mx << " | " << tree[v].mn << "!\n";
a[lv] = max(a[lv], tree[v].mx);
a[lv] = min(a[lv], tree[v].mn);
}
else
{
// cout << lv << " | " << v << " " << tree[v].mn << " " << tree[v].mx << "!\n";
a[lv] = min(a[lv], tree[v].mn);
a[lv] = max(a[lv], tree[v].mx);
}
}
return;
}
int m = (lv + rv) >> 1;
push(v);
outArray(a, v * 2 + 1, lv, m);
outArray(a, v * 2 + 2, m, rv);
}
void outArray(vector<int> &a)
{
outArray(a, 0, 0, sz);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
vector<int> a;
for (int i = 0; i < n; ++i)
a.push_back(finalHeight[i]);
segTree tree;
tree.init(n);
for (int i = 0; i < k; ++i)
{
op[i]--;
tree.addOp(left[i], right[i] + 1, {1 - op[i], height[i]});
}
tree.outArray(a);
for (int i = 0; i < n; ++i)
finalHeight[i] = a[i];
return;
}
// int main()
// {
// int n;
// int k;
// int i, j;
// int status = 0;
// status = scanf("%d%d", &n, &k);
// assert(status == 2);
// int *op = (int *)calloc(sizeof(int), k);
// int *left = (int *)calloc(sizeof(int), k);
// int *right = (int *)calloc(sizeof(int), k);
// int *height = (int *)calloc(sizeof(int), k);
// int *finalHeight = (int *)calloc(sizeof(int), n);
// for (i = 0; i < k; i++)
// {
// status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
// assert(status == 4);
// }
// buildWall(n, k, op, left, right, height, finalHeight);
// for (j = 0; j < n; j++)
// printf("%d\n", finalHeight[j]);
// return 0;
// }
