#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int off = (1<<21);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
pii t[off * 2];
pii unit = {0, inf};
void init(){
for (int i = 0; i < off * 2; i++){
t[i] = unit;
}
}
pii merge(pii lhs, pii rhs){
// lhs.S rhs.S
// lhs.F rhs.F
if (lhs.F > rhs.S){
return {rhs.S, rhs.S};
}
if (rhs.F > lhs.S){
return {rhs.F, rhs.F};
}
return {max(lhs.F, rhs.F), min(lhs.S, rhs.S)};
}
void push(int idx){
if (t[idx] == unit || idx >= off) return;
t[ls] = merge(t[ls], t[idx]);
t[rs] = merge(t[rs], t[idx]);
t[idx] = unit;
}
void update(int l, int r, int op, int val, int idx=1, int lo=0, int hi=off){
push(idx);
if (r <= lo || hi <= l)
return;
if (l <= lo && hi <= r){
if (op == 1){
t[idx] = merge(t[idx], {val, inf});
} else if (op == 2){
t[idx] = merge(t[idx], {0, val});
}
return;
}
int mi = (lo+hi)>>1;
update(l, r, op, val, ls, lo, mi);
update(l, r, op, val, rs, mi, hi);
return;
}
void updateAll(){
for (int i = 0; i < off; i++){
push(i);
}
}
void printO(){
int pw = 1;
int cnt = 0;
for (int i = 1; i < off * 2; i++){
cnt++;
cout << "("<< (t[i].F == inf ? -1 : t[i].F) << ", " << (t[i].S == inf ? -1 : t[i].S) << ") ";
if (cnt == pw){
pw *= 2;
cnt = 0 ;
cout << endl;
}
}
}
void print(int n){
updateAll();
for (int i = 0; i < n; i++){
cout << "("<< (t[i + off].F == inf ? -1 : t[i + off].F) << ", " << (t[i + off].S == inf ? -1 : t[i + off].S) << ") ";
}
cout << endl;
}
} seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
seg.init();
//seg.printO();
for (int i = 0; i < k; i++){
seg.update(left[i], right[i] + 1, op[i], height[i]);
//seg.printO();
//seg.print(n);
}
seg.updateAll();
for (int i = 0; i < n; i++){
finalHeight[i] = seg.t[i + off].F;
}
}
