// M
#include<bits/stdc++.h>
#include "wall.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 2000006, MXS = N * 4, MXH = 1e5 + 3;
int n, MN[MXS], MX[MXS];
int * RS;
inline void Apply(int id, int mn, int mx)
{
assert(mn >= mx);
// mn :
MN[id] = min(MN[id], mn);
if (MX[id] > MN[id]) MX[id] = mn;
// mx :
MX[id] = max(MX[id], mx);
if (MN[id] < MX[id]) MN[id] = mx;
}
inline void Shift(int id)
{
Apply(lc, MN[id], MX[id]);
Apply(rc, MN[id], MX[id]);
MN[id] = MXH;
MX[id] = 0;
}
void Add(int le, int ri, int mn, int mx, int id = 1, int l = 0, int r = n)
{
if (ri <= l || r <= le)
return ;
if (le <= l && r <= ri)
return void(Apply(id, mn, mx));
Shift(id);
Add(le, ri, mn, mx, lc, l, md);
Add(le, ri, mn, mx, rc, md, r);
}
void DFS(int id = 1, int l = 0, int r = n)
{
if (r - l < 2)
return void(RS[l] = MX[id]);
Shift(id);
DFS(lc, l, md);
DFS(rc, md, r);
}
void buildWall(int _n, int q, int * op, int * le, int * ri, int * A, int * Rs)
{
n = _n; RS = Rs;
for (int i = 0; i < q; i ++)
{
if (op[i] == 1)
Add(le[i], ri[i] + 1, MXH, A[i]);
else
Add(le[i], ri[i] + 1, A[i], 0);
}
DFS();
}
