#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2E6;
int t[4*N],lazy[4*N][2],l,r,val;// min h, max h
bool type;
void push(int v,int tl,int tr) {
if (lazy[v][0]) {
if (lazy[v*2][0] < lazy[v][0]){
lazy[v*2][0] = lazy[v][0];
if (t[v*2] < lazy[v][0]) t[v*2] = lazy[v][0];
}
if (lazy[v*2|1][0] < lazy[v][0]) {
lazy[v*2|1][0] = lazy[v][0];
if (t[v*2|1] < lazy[v][0]) t[v*2|1] = lazy[v][0];
}
if (lazy[v*2][0] > lazy[v*2][1]) {
lazy[v*2][1] = lazy[v*2][0];
}
if (lazy[v*2|1][0] > lazy[v*2|1][1] ) {
lazy[v*2|1][1] = lazy[v*2|1][0];
}
lazy[v][0] = 0;
}
if (lazy[v][1] != 1e9) {
if (lazy[v*2][1] > lazy[v][1]) {
lazy[v*2][1] = lazy[v][1];
lazy[v*2][0] = min (lazy[v*2][0],lazy[v*2][1]);
if (t[v*2] > lazy[v][1]) t[v*2] = lazy[v][1];
}
if (lazy[v*2|1][1] > lazy[v][1]) {
lazy[v*2|1][1] = lazy[v][1];
lazy[v*2|1][0] = min (lazy[v*2|1][0],lazy[v*2|1][1]);
if (t[v*2|1] > lazy[v][1]) t[v*2|1] = lazy[v][1];
}
lazy[v][1] = 1e9;
}
}
void upd (int v,int tl,int tr) {
if (l > tr || r < tl) return;
if (tl >= l && tr <= r) {
if (type == 0) {
if (lazy[v][0] >= val) return;
t[v] = max (t[v],val);
lazy[v][0] = max (lazy[v][0],val);
if (lazy[v][1] < lazy[v][0]) {
lazy[v][1] = lazy[v][0];
}
}
else {
if (lazy[v][1] <= val) return;
lazy[v][1] = val;
if (lazy[v][0] > lazy[v][1]) {
lazy[v][0] = lazy[v][1];
}
t[v] = min(t[v],lazy[v][1]);
}
return;
}
push (v,tl,tr);
int tm = (tl + tr)/2;
upd (v*2,tl,tm);
upd (v*2|1,tm+1,tr);
t[v] = min(t[v*2],t[v*2|1]);
}
int A[N];
void get (int v,int tl,int tr) {
if (tl == tr) A[tl] = t[v];
else {
int tm = (tl + tr)/2;
push(v,tl,tr);
get(v*2,tl,tm);
get(v*2+1,tm+1,tr);
}
}
void buildWall(int n,int k,int op[],int left1[],int right1[],int height[],int finalHeight[]) {
for (int i = 0; i < 4*N; i++) lazy[i][1] = 1e9,t[i] = 1,lazy[i][0] = 1;
for (int i = 0; i < k; i++) {
type = op[i] - 1;
l = left1[i];
r = right1[i];
val = height[i] + 1;
upd (1,0,n-1);
}
get(1,0,n-1);
for (int i = 0;i < n; i++)
finalHeight[i] = max (A[i] - 1,0);
} /*
main() { /*
freopen("wads.txt","r",stdin);
freopen("wall.out","w",stdout);
cin >> n;
cin >> k;
for (int i = 0; i < k; i++) {
cin >> op[i] >> left1[i] >> right1[i] >> height[i];
}
//cout <<
buildWall();
for (int i = 0; i < n; i++) cout << finalHeight[i] <<'\n';
return 0;
} */
/* 10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
