#include "wall.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;
const int nmax = 2000005;
int mini[4*nmax], maxi[4*nmax], lazy[4*nmax];
vector<int>ans;
void push(int l, int r, int nod){
if(lazy[nod]){
if(maxi[nod] < mini[2 * nod]) mini[2 * nod] = maxi[nod];
else mini[2 * nod] = max(mini[2 * nod], mini[nod]);
if(mini[nod] > maxi[2 * nod]) maxi[2 * nod] = mini[nod];
else maxi[2 * nod] = min(maxi[2 * nod], maxi[nod]);
if(maxi[nod] < mini[2 * nod + 1]) mini[2 * nod + 1] = maxi[nod];
else mini[2 * nod + 1] = max(mini[2 * nod + 1], mini[nod]);
if(mini[nod] > maxi[2 * nod + 1]) maxi[2 * nod + 1] = mini[nod];
else maxi[2 * nod + 1] = min(maxi[2 * nod + 1], maxi[nod]);
int mid = l + (r - l) / 2;
if(l != mid) lazy[2 * nod] = 1;
if(mid + 1 != r) lazy[2 * nod + 1] = 1;
}
lazy[nod] = 0;
}
void update(int l, int r, int le, int ri, int op, int val, int nod){
push(l, r, nod);
if(r < le || l > ri) return;
else if(l >= le && r <= ri){
if(op == 1){
mini[nod] = max(mini[nod], val);
maxi[nod] = max(maxi[nod], val);
}
else{
maxi[nod] = min(maxi[nod], val);
mini[nod] = min(mini[nod], val);
}
if(l != r) lazy[nod] = 1;
}
else{
int mid = l + (r - l) / 2;
update(l, mid, le, ri, op, val, 2*nod);
update(mid + 1, r, le, ri, op, val, 2 * nod + 1);
mini[nod] = min(mini[2 * nod], mini[2 * nod + 1]);
maxi[nod] = max(maxi[2 * nod], maxi[2 * nod + 1]);
}
}
void dfs(int l, int r, int nod){
push(l, r, nod);
if(l == r) ans[l] = mini[nod];
else{
int mid = l + (r - l) / 2;
dfs(l, mid, 2 * nod);
dfs(mid + 1, r, 2 * nod + 1);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++){
update(1, n, left[i] + 1, right[i] + 1, op[i], height[i], 1);
}
ans.resize(n + 1);
dfs(1, n, 1);
for(int i=0;i<n;i++) finalHeight[i] = ans[i + 1];
return;
}
