#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<long, long> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MAXK = 500000;
const int MAXH = 100000;
const int MAXN = (int)(2e6);
int maxTree[4*MAXK+5];
int minTree[4*MAXK+5];
vector<int> row[MAXN+5];
void turn(int n, int tl, int tr, int v, bool add, int chg) {
if (tl != tr) {
int tm = (tl + tr)/2;
if (v <= tm) {
turn(2*n, tl, tm, v, add, chg);
}
else {
turn(2*n+1, tm+1, tr, v, add, chg);
}
maxTree[n] = max(maxTree[2*n], maxTree[2*n+1]);
minTree[n] = min(minTree[2*n], minTree[2*n+1]);
}
else {
int i = n;
if ((maxTree[i] != -1) || (minTree[i] != MAXH+5)) {
maxTree[i] = -1;
minTree[i] = MAXH+5;
}
else {
if (add) {
maxTree[i] = chg;
}
else {
minTree[i] = chg;
}
}
}
}
int get(int n, int tl, int tr, int ma, int mi) {
if (tl == tr) {
if (maxTree[n] != -1) {
return mi;
}
else {
return ma;
}
}
else {
int tm = (tl + tr)/2;
if (max(ma, maxTree[2*n+1]) < min(mi, minTree[2*n+1])) {
ma = max(ma, maxTree[2*n+1]);
mi = min(mi, minTree[2*n+1]);
return get(2*n, tl, tm, ma, mi);
}
else {
return get(2*n+1, tm+1, tr, ma, mi);
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int i = 0; i < 4*MAXK+5; i++) {
maxTree[i] = -1;
minTree[i] = MAXH+5;
}
FR(i, k) {
row[left[i]].push_back(i);
row[right[i]+1].push_back(i);
}
FR(i, n) {
for (auto& p : row[i]) {
turn(1, 0, k-1, p, (op[p] == 1), height[p]);
}
if (maxTree[1] < minTree[1]) {
if (maxTree[1] == -1) {
finalHeight[i] = 0;
}
else {
finalHeight[i] = maxTree[1];
}
}
else {
finalHeight[i] = get(1, 0, k-1, -1, MAXH+5);
}
}
}
//int op[101];
//int l[101];
//int r[101];
//int h[101];
//int fH[101];
//int main() {
// int n, k;
// cin >> n >> k;
// FR(i, k) {
// cin >> op[i] >> l[i] >> r[i] >> h[i];
// }
// buildWall(n, k, op, l, r, h, fH);
// FR(i, n) {
// cout << fH[i] << endl;
// }
//}
