#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define orta ((bas+son)>>1)
#define N 2000005
struct SEG {
int mn,mx;
} S[N*4];
int lazy[N*4];
int n;
SEG merge(SEG x,SEG y) {
return {min(x.mn,y.mn),max(x.mx,y.mx)};
}
void push(int node,int bas,int son) {
if(~lazy[node]) {
S[node*2].mx=S[node*2].mn=S[node*2+1].mx=S[node*2+1].mn=lazy[node*2]=lazy[node*2+1]=lazy[node];
lazy[node]=-1;
}
}
SEG get(int node,int bas,int son,int x) {
if(bas==x && son==x) return S[node];
push(node,bas,son);
if(orta>=x) return get(node*2,bas,orta,x);
return get(node*2+1,orta+1,son,x);
}
void up(int node,int bas,int son,int l,int r,int h,int typ) {
if(bas>r || son<l) return ;
if(typ==1) {
if(S[node].mn>=h) return ;
}
else {
if(S[node].mx<=h) return ;
}
if(bas>=l && son<=r) {
if(typ==1) {
if(S[node].mx<=h) {
S[node].mx=S[node].mn=h;
lazy[node]=h;
return ;
}
}
else {
if(S[node].mn>=h) {
S[node].mn=S[node].mx=h;
lazy[node]=h;
return ;
}
}
}
if(bas==son) return ;
push(node,bas,son);
up(node*2,bas,orta,l,r,h,typ);
up(node*2+1,orta+1,son,l,r,h,typ);
S[node]=merge(S[node*2],S[node*2+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(lazy,-1,sizeof(lazy));
::n=n;
for(int i=0;i<k;i++) {
up(1,0,n-1,left[i],right[i],height[i],op[i]);
}
for(int i=0;i<n;i++) {
finalHeight[i]=get(1,0,n-1,i).mx;
}
}
/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "wall.h"
int main()
{
freopen("sample-2.in","r",stdin);
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}
*/
