#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define rint int32_t
const int pow2 = 1<<21;
int minLz [pow2*2];
int maxLz [pow2*2];
void btClear() {
for (int i = 0; i < pow2*2; i++) {
minLz[i] = 0;
maxLz[i] = 100000;
}
}
void btPrpg(int qNode) {
if (qNode >= pow2) return;
if (minLz[qNode*2] < minLz[qNode]) minLz[qNode*2] = minLz[qNode];
if (maxLz[qNode*2] > maxLz[qNode]) maxLz[qNode*2] = maxLz[qNode];
if (minLz[qNode*2] > maxLz[qNode*2]) {
if (minLz[qNode*2] <= minLz[qNode]) maxLz[qNode*2] = minLz[qNode];
else minLz[qNode*2] = maxLz[qNode];
}
if (minLz[qNode*2+1] < minLz[qNode]) minLz[qNode*2+1] = minLz[qNode];
if (maxLz[qNode*2+1] > maxLz[qNode]) maxLz[qNode*2+1] = maxLz[qNode];
if (minLz[qNode*2+1] > maxLz[qNode*2+1]) {
if (minLz[qNode*2+1] <= minLz[qNode]) maxLz[qNode*2+1] = minLz[qNode];
else minLz[qNode*2+1] = maxLz[qNode];
}
minLz[qNode] = 0;
maxLz[qNode] = 100000;
}
void btUpdate(int rBegin, int rEnd, int rUp, int rVal, int qNode, int qBegin, int qEnd) {
if (rBegin > qEnd or qBegin > rEnd) return;
else if (rBegin <= qBegin and qEnd <= rEnd) {
if (rUp == 1 and minLz[qNode] < rVal) {
minLz[qNode] = rVal;
if (minLz[qNode] > maxLz[qNode]) {
maxLz[qNode] = rVal;
}
}
else if (rUp == 2 and maxLz[qNode] > rVal) {
maxLz[qNode] = rVal;
if (minLz[qNode] > maxLz[qNode]) {
minLz[qNode] = rVal;
}
}
btPrpg(qNode);
}
else {
btPrpg(qNode);
int qMid = (qBegin+qEnd)/2;
btUpdate(rBegin, rEnd, rUp, rVal, qNode*2, qBegin, qMid);
btUpdate(rBegin, rEnd, rUp, rVal, qNode*2+1, qMid+1, qEnd);
}
}
void buildWall(int n, int nbReq, int up [], int left [], int right [], int height [], int res []) {
btClear();
for (int i = 0; i < n; i++) btUpdate(i, i, 2, 0, 1, 0, pow2-1);
for (int i = 0; i < nbReq; i++) {
// if (up[i] == 2) continue;
btUpdate(left[i], right[i], up[i], height[i], 1, 0, pow2-1);
}
for (int i = 0; i < n; i++) {
btUpdate(i, i, 1, 0, 1, 0, pow2-1);
res[i] = minLz[pow2+i];
// cout << "--> " << minLz[pow2+i] << " - " << maxLz[pow2+i] << endl; // dbg info
}
int d = 0;
d++;
}
// rint main() {
// cin.tie(0);
// ios_base::sync_with_stdio(0);
// int n = 10;
// int nbReq = 6;
// int up [6] = {1, 2, 2, 1, 1, 2};
// int left [6] = {1, 4, 3, 0, 2, 6};
// int right [6] = {8, 9, 6, 5, 2, 7};
// int height [6] = {4, 1, 5, 3, 5, 0};
// int res [6];
// buildWall(n, nbReq, up, left, right, height, res);
// int d = 0;
// d++;
// }
