#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 2000005
int ans[maxn];
int L[maxn*4], R[maxn*4];
void upd(int pos,int l,int r) {
L[pos] = max(L[pos], l);
L[pos] = min(L[pos], r);
R[pos] = max(R[pos], l);
R[pos] = min(R[pos], r);
}
void update(int pos,int l,int r,int x,int y,int val,int type) {
if(l!=r) {
upd(pos<<1,L[pos],R[pos]);
upd(pos<<1|1,L[pos],R[pos]);
}
if(l>r || y<l || r<x) return ;
if(x<=l && r<=y) {
if(type==1) {
L[pos] = max(L[pos], val);
R[pos] = max(R[pos], val);
}
else {
L[pos] = min(L[pos], val);
R[pos] = min(R[pos], val);
}
return ;
}
int mid = (l+r)/2;
update(pos<<1,l,mid,x,y,val,type); update(pos<<1|1,mid+1,r,x,y,val,type);
L[pos] = min(L[pos<<1], L[pos<<1|1]);
R[pos] = max(R[pos<<1], R[pos<<1|1]);
}
void query(int pos,int l,int r) {
if(l!=r) {
upd(pos<<1,L[pos],R[pos]);
upd(pos<<1|1,L[pos],R[pos]);
}
if(l==r) {
ans[l] = L[pos];
return ;
}
int mid = (l+r)/2;
query(pos<<1,l,mid); query(pos<<1|1,mid+1,r);
}
void buildWall(int n, int m, int type[], int l[], int r[], int val[], int ret[]) {
int i;
for(i=0;i<m;i++) update(1,0,n-1,l[i],r[i],val[i],type[i]);
query(1,0,n-1);
for(i=0;i<n;i++) ret[i] = ans[i];
return ;
}
