#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
#define INF 100005
int v[2000005],l,r;
pair<int,int> q;
pair<int,int> rt[9000000];
inline pair<int,int> unite(pair<int,int> a,pair<int,int> b){
pair<int,int> tmp;
tmp.second=max(b.first,min(b.second,a.second));
tmp.first=min(b.second,max(b.first,a.first));
return tmp;
}
inline void push(int pos){
rt[pos*2]=unite(rt[pos],rt[pos*2]);
rt[pos*2+1]=unite(rt[pos],rt[pos*2+1]);
rt[pos]={0,INF};
}
void upd(int pos,int _l,int _r){
if(r<_l || l>_r)return;
if(_l>=l && _r<=r){
rt[pos]=unite(q,rt[pos]);
return;
}
push(pos);
upd(pos*2,_l,(_l+_r)/2);
upd(pos*2+1,(_l+_r)/2+1,_r);
}
void query(int pos,int _l,int _r,int val){
if(val<rt[pos].first)val=rt[pos].first;
if(val>rt[pos].second)val=rt[pos].second;
if(_l==_r){
v[_l]=val;
return;
}
query(pos*2,_l,(_l+_r)/2,val);
query(pos*2+1,(_l+_r)/2+1,_r,val);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<9000000;i++)rt[i].second=INF;
for(int i=k-1;i>=0;i--){
l=left[i];
r=right[i];
if(op[i]==1){
q.first=height[i];
q.second=INF;
}
else{
q.first=0;
q.second=height[i];
}
upd(1,0,n-1);
}
query(1,0,n-1,0);
for(int i=0;i<n;i++){
finalHeight[i]=v[i];
}
return;
}
/*
int main()
{
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;
}*/
