#include<bits/stdc++.h>
#include "wall.h"
#define pb push_back
#define mp make_pair
using namespace std;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
struct SEGT{
vector<int> mx, mn, lazy;
void init(int n){
lazy.assign(4*n, -1);
mx.assign(4*n, 0);
mn.assign(4*n, 0);
}
void push(int ind){
if(lazy[ind] == -1) return;
mx[ind*2] = lazy[ind];
mx[ind*2+1] = lazy[ind];
mn[ind*2] = lazy[ind];
mn[ind*2+1] = lazy[ind];
lazy[ind*2] = lazy[ind];
lazy[ind*2+1] = lazy[ind];
lazy[ind] = -1;
}
void update1(int ind, int l, int r, int ql, int qr, int val){
if(l > r || l > qr || r < ql) return;
if(l >= ql && r <= qr && mx[ind] <= val){
lazy[ind] = val;
mx[ind] = val;
mn[ind] = val;
}
else if(l >= ql && r <= qr && mn[ind] >= val) return;
else if(l == r){
mx[ind] = max(mx[ind], val);
mn[ind] = mx[ind];
}
else{
push(ind);
int m = (l + r)/2;
update1(ind*2, l, m, ql, qr, val);
update1(ind*2+1, m+1, r, ql, qr, val);
mx[ind] = max(mx[ind*2], mx[ind*2+1]);
mn[ind] = min(mn[ind*2], mn[ind*2+1]);
}
}
void update2(int ind, int l, int r, int ql, int qr, int val){
if(l > r || l > qr || r < ql) return;
if(l >= ql && r <= qr && mn[ind] >= val){
lazy[ind] = val;
mx[ind] = val;
mn[ind] = val;
}
else if(l >= ql && r <= qr && mx[ind] <= val) return;
else if(l == r){
mx[ind] = max(mx[ind], val);
mn[ind] = mx[ind];
}
else{
push(ind);
int m = (l + r)/2;
update2(ind*2, l, m, ql, qr, val);
update2(ind*2+1, m+1, r, ql, qr, val);
mx[ind] = max(mx[ind*2], mx[ind*2+1]);
mn[ind] = min(mn[ind*2], mn[ind*2+1]);
}
}
void query(int ind, int l, int r, vector<int> &a){
if(l == r) a[l] = mx[ind];
else{
push(ind);
int m = (l + r)/2;
query(ind*2, l, m, a);
query(ind*2+1, m+1, r, a);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SEGT seg;
seg.init(n);
for(int i = 0; i < k; i++){
if(op[i] == 1) seg.update1(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
else seg.update2(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
}
vector<int> a(n+1);
seg.query(1, 1, n, a);
for(int i = 0; i < n; i++){
finalHeight[i] = a[i+1];
}
}
/*
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;
}
*/
