#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
vector<int> st;
vector<array<int, 2>> lazy;
void push(int l, int r, int x){
if(l == r){
st[x] = max(st[x], lazy[x][0]);
st[x] = min(st[x], lazy[x][1]);
lazy[x] = {-1, INT_MAX};
return;
}
lazy[2 * x + 1][0] = max(lazy[2 * x + 1][0], lazy[x][0]);
lazy[2 * x + 1][1] = max(lazy[2 * x + 1][1], lazy[x][0]);
lazy[2 * x + 1][0] = min(lazy[2 * x + 1][0], lazy[x][1]);
lazy[2 * x + 1][1] = min(lazy[2 * x + 1][1], lazy[x][1]);
lazy[2 * x + 2][0] = max(lazy[2 * x + 2][0], lazy[x][0]);
lazy[2 * x + 2][1] = max(lazy[2 * x + 2][1], lazy[x][0]);
lazy[2 * x + 2][0] = min(lazy[2 * x + 2][0], lazy[x][1]);
lazy[2 * x + 2][1] = min(lazy[2 * x + 2][1], lazy[x][1]);
lazy[x] = {-1, INT_MAX};
}
void update(int lq, int rq, int l, int r, int i, int to, int x){
push(l, r, x);
if(lq > r || l > rq) return;
if(lq <= l && r <= rq){
lazy[x][i] = to;
return;
}
int mid = (l + r) / 2;
update(lq, rq, l, mid, i, to, 2 * x + 1);
update(lq, rq, mid + 1, r, i, to, 2 * x + 2);
}
int query(int i, int l, int r, int x){
push(l, r, x);
if(l == r){
return st[x];
}
int mid = (l + r) / 2;
if(i <= mid) return query(i, l, mid, 2 * x + 1);
else return query(i, mid + 1, r, 2 * x + 2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
st.resize(4 * n + 4, 0);
lazy.resize(4 * n + 4, {-1, INT_MAX});
for(int i = 0; i < k; i++){
update(left[i], right[i], 0, n, op[i] - 1, height[i], 0);
}
for(int i = 0; i < n; i++) finalHeight[i] = query(i, 0, n, 0);
//for(int i = 0; i < n; i++) cout << finalHeight[i] << " ";
}
/*
int main(){
int n, k;
cin >> n >> k;
int op[k];
int left[k];
int right[k];
int height[k];
int f[n];
for(int i = 0; i < k; i++) cin >> op[i] >> left[i] >> right[i] >> height[i];
buildWall(n, k, op, left, right, height, f);
}
*/
