//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "wall.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
struct node
{
int lo, hi;
node()
{
lo = 0; hi = 1e5;
}
};
const int maxn = 2e6+5;
node st[4*maxn];
int n;
void change(int p, int op, int v)
{
if(op == 1) st[p].lo = max(st[p].lo, v), st[p].hi = max(st[p].hi, v);
else st[p].lo = min(st[p].lo, v), st[p].hi = min(st[p].hi, v);
}
void update(int i, int j, int op, int v, int p = 1, int L = 0, int R = n-1)
{
if(i> R || j< L) return;
if(i<= L && R<= j)
{
change(p, op, v);
return;
}
change(2*p, 1, st[p].lo); change(2*p+1, 1, st[p].lo);
change(2*p, 2, st[p].hi); change(2*p+1, 2, st[p].hi);
st[p].lo = 0, st[p].hi = 1e5;
int M = (L+R)/2;
update(i, j, op, v, 2*p, L, M);
update(i, j, op, v, 2*p+1, M+1, R);
}
int *arr;
void prop(int p = 1, int L = 0, int R = n-1)
{
if(L == R)
{
arr[L] = st[p].lo;
return;
}
change(2*p, 1, st[p].lo); change(2*p+1, 1, st[p].lo);
change(2*p, 2, st[p].hi); change(2*p+1, 2, st[p].hi);
int M = (L+R)/2;
prop(2*p, L, M); prop(2*p+1, M+1, R);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
n = N;
arr = finalHeight;
for(int i = 0; i< k; i++) update(left[i], right[i], op[i], height[i]);
prop();
}
