#include <bits/stdc++.h>
#include <wall.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"
const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
// -------------------------------------------------- Main Code --------------------------------------------------
struct Node {
int val, mn, mx; // final value, last was delete oper, last was add oper
};
struct segTree {
int n;
vector<Node> tree;
segTree(int N) {n = 1; while (n < N) n *= 2; tree = vector<Node>(2*n+2, {0, inf, -1});}
void propogate(int node, int left, int right) {
if (tree[node].mn == inf && tree[node].mx == -1) return;
if (tree[node].mn != inf) {
tree[node].val = min(tree[node].val, tree[node].mn);
if (left != right) {
tree[node*2].mx = min(tree[node].mn, tree[node*2].mx);
tree[node*2].mn = min(tree[node].mn, tree[node*2].mn);
tree[node*2+1].mx = min(tree[node].mn, tree[node*2+1].mx);
tree[node*2+1].mn = min(tree[node].mn, tree[node*2+1].mn);
}
tree[node].mn = inf;
}
if (tree[node].mx != -1) {
tree[node].val = max(tree[node].val, tree[node].mx);
if (left != right) {
tree[node*2].mn = max(tree[node].mx, tree[node*2].mn);
tree[node*2].mx = max(tree[node].mx, tree[node*2].mx);
tree[node*2+1].mn = max(tree[node].mx, tree[node*2+1].mn);
tree[node*2+1].mx = max(tree[node].mx, tree[node*2+1].mx);
}
tree[node].mx = -1;
}
}
void update(int node, int left, int right, int l, int r, int val, int type) {
propogate(node, left, right);
if (left > r || right < l) return;
else if (left >= l && right <= r) {
if (type == 1) {
// add operation
tree[node].mn = inf;
tree[node].mx = val;
}
else {
// delete operation
tree[node].mn = val;
tree[node].mx = -1;
}
propogate(node, left, right);
return;
}
update(node*2, left, (left+right)/2, l, r, val, type);
update(node*2+1, (left+right)/2+1, right, l, r, val, type);
}
void update(int l, int r, int val, int type) {update(1, 1, n, l, r, val, type);}
int query(int node, int left, int right, int idx) {
propogate(node, left, right);
if (left == right) {
return tree[node].val;
}
int mid = (left+right)/2;
if (idx <= mid) return query(node*2, left, (left+right)/2, idx);
else return query(node*2+1, (left+right)/2+1, right, idx);
}
int query(int idx) {return query(1, 1, n, idx);}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segTree tree(n);
for (int i = 0; i < k; i++) tree.update(left[i]+1, right[i]+1, height[i], op[i]);
for (int i = 0; i < n; i++) finalHeight[i] = tree.query(i+1);
}
