#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int c=1<<22, sok=1e9;
int kezd[c], veg[c], kis[c], nagy[c];
int s(int a, int l, int r) {
if (r<kezd[a] || l>veg[a]) return 0;
if (l<=kezd[a] && veg[a]<=r) return 2;
return 1;
}
void push(int a) {
int x=2*a, y=2*a+1;
kis[x]=min(nagy[a], max(kis[x], kis[a]));
nagy[x]=max(kis[a], min(nagy[x], nagy[a]));
kis[y]=min(nagy[a], max(kis[y], kis[a]));
nagy[y]=max(kis[a], min(nagy[y], nagy[a]));
kis[a]=0, nagy[a]=sok;
}
void add(int a, int l, int r, int ert, int f) {
int p=s(a, l, r);
if (!p) return;
if (p==2) {
if (f==1) {
kis[a]=max(kis[a], ert);
nagy[a]=max(nagy[a], ert);
} else {
kis[a]=min(kis[a], ert);
nagy[a]=min(nagy[a], ert);
}
return;
}
push(a);
add(2*a, l, r, ert, f), add(2*a+1, l, r, ert, f);
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
int po=1;
while (po<=n) po*=2;
for (int i=po; i<2*po; i++) {
kezd[i]=veg[i]=i-po;
nagy[i]=sok;
}
for (int i=po-1; i>=1; i--) {
kezd[i]=kezd[2*i], veg[i]=veg[2*i+1];
nagy[i]=sok;
}
for (int i=0; i<k; i++) {
add(1, l[i], r[i], h[i], op[i]);
}
for (int i=1; i<po; i++) {
push(i);
}
for (int i=po; i<po+n; i++) {
ans[i-po]=kis[i];
}
return;
}
