#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
using namespace std;
const int sz = 2e6 + 9;
const int INF = 1e9;
int tmax[sz << 2], tmin[sz << 2];
void add(int pos, int maxi, int mind)
{
if (tmax[pos] > mind)
tmax[pos] = tmin[pos] = mind;
else if (tmin[pos] < maxi)
tmax[pos] = tmin[pos] = maxi;
else
{
tmax[pos] = max(tmax[pos], maxi);
tmin[pos] = min(tmin[pos], mind);
}
}
void push(int pos, int ind, int fim)
{
if (ind != fim)
{
add(pos << 1, tmax[pos], tmin[pos]);
add(pos << 1 | 1, tmax[pos], tmin[pos]);
tmax[pos] = 0;
tmin[pos] = INF;
}
}
void upd(int pos, int ind, int fim, int l, int r, int maxi, int mind)
{
push(pos, ind, fim);
if (l <= ind && fim <= r)
{
add(pos, maxi, mind);
push(pos, ind, fim);
return;
}
if (r < ind || fim < l)
{
return;
}
int m = (ind + fim) >> 1;
upd(pos << 1, ind, m, l, r, maxi, mind);
upd(pos << 1 | 1, m + 1, fim, l, r, maxi, mind);
}
void build(int pos, int ind, int fim, int res[])
{
if (ind == fim)
{
res[ind] = tmax[pos];
return;
}
push(pos, ind, fim);
int m = (ind + fim)/2;
build(pos << 1, ind, m, res);
build(pos << 1 | 1, m + 1, fim, res);
}
void buildWall(int n, int q, int op[], int ls[], int rs[], int hs[], int res[])
{
for (int i = 1; i <= (n << 2); ++i)
{
tmin[i] = INF;
}
for (int i = 0; i < q; ++i)
{
if (op[i] == 1)
{
upd(1, 0, n-1, ls[i], rs[i], hs[i], INF);
}
else
{
upd(1, 0, n-1, ls[i], rs[i], 0, hs[i]);
}
}
build(1, 0, n-1, res);
}
