#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "wall.h"
PII perform(PII a, PII b) {
PII ret = {max(a.ff, b.ff), min(a.ss, b.ss)};
if (ret.ff > ret.ss) {
if (b.ff > a.ss) return {b.ff, b.ff};
return {b.ss, b.ss};
}
return ret;
}
struct SEGTREE {
int n;
VPI tree;
VPI lazy;
SEGTREE(int sz) {
n = 1;
while (n < sz) n *= 2;
tree = VPI(2*n, {0, +1e9});
lazy = VPI(2*n, {0, +1e9});
}
void push(int N) {
if (N < n-1) {
lazy[2*N+1] = perform(lazy[2*N+1], lazy[N]);
lazy[2*N+2] = perform(lazy[2*N+2], lazy[N]);
} else {
tree[N] = perform(tree[N], lazy[N]);
}
lazy[N] = {0, +1e9};
}
void setmx(int N, int L, int R, int l, int r, int h) {
push(N);
if (R < l || L > r) return;
if (l <= L && R <= r) {
lazy[N] = {0, h};
push(N);
return;
}
int M = (L+R)/2;
setmx(2*N+1, L, M, l, r, h);
setmx(2*N+2, M+1, R, l, r, h);
}
void setmn(int N, int L, int R, int l, int r, int h) {
push(N);
if (R < l || L > r) return;
if (l <= L && R <= r) {
lazy[N] = {h, +1e9};
push(N);
return;
}
int M = (L+R)/2;
setmn(2*N+1, L, M, l, r, h);
setmn(2*N+2, M+1, R, l, r, h);
}
void print(int N, int L, int R) {
if (N > 2*n-2) return;
cout << N << "," << L+1 << ".." << R+1 << ": " << lazy[N].ff << ".." << lazy[N].ss << endl;
int M = (L+R)/2;
print(2*N+1, L, M);
print(2*N+2, M+1, R);
}
void print() {
print(0, 0, n-1);
replr(i, n-1, 2*n-2) {
cout << tree[i].ff << ".." << tree[i].ss << endl;
}
}
void finish(int N = 0) {
if (N > 2*n-2) return;
push(N);
finish(2*N+1);
finish(2*N+2);
}
VI verj() {
VI ret;
replr(i, n-1, 2*n-2) ret.pb(tree[i].ff);
return ret;
}
void setmx(int l, int r, int h) {
setmx(0, 0, n-1, l, r, h);
}
void setmn(int l, int r, int h) {
setmn(0, 0, n-1, l, r, h);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SEGTREE seg(n);
for (int i = 0; i < k; i++) {
int l = left[i];
int r = right[i];
int h = height[i];
/*l--, r--;*/
if (op[i] == 1) seg.setmn(l, r, h);
else seg.setmx(l, r, h);
/*seg.print();*/
/*cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAa" << endl;*/
}
seg.finish();
VI ans = seg.verj();
rep(i, n) finalHeight[i] = ans[i];
}
