#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool hasLazy[8000005];
struct SegmentTree {
vector<int> tree[2], minLazy, maxLazy;
void build(int N, int idx, int l, int r) {
if (idx == 1) {
tree[0].resize(4 * N);
tree[1].resize(4 * N);
minLazy.resize(4 * N);
maxLazy.resize(4 * N);
fill(tree[1].begin(), tree[1].begin() + 4 * N, 1e9);
}
maxLazy[idx] = 1e9;
if (l != r) {
int mid = (l + r) >> 1;
build(N, idx * 2, l, mid);
build(N, idx * 2 + 1, mid + 1, r);
}
return;
}
void push(int idx, int l, int r) {
if (!hasLazy[idx]) return;
int mid = (l + r) >> 1;
tree[0][idx] = max(minLazy[idx], tree[0][idx]);
tree[1][idx] = min(maxLazy[idx], tree[1][idx]);
if (l != r) {
minLazy[2*idx] = min(maxLazy[idx], max(minLazy[idx], minLazy[2*idx]));
maxLazy[2*idx] = min(maxLazy[idx], max(minLazy[idx], maxLazy[2*idx]));
minLazy[2*idx+1] = min(maxLazy[idx], max(minLazy[idx], minLazy[2*idx+1]));
maxLazy[2*idx+1] = min(maxLazy[idx], max(minLazy[idx], maxLazy[2*idx+1]));
hasLazy[2*idx+1] = hasLazy[2*idx] = 1;
}
hasLazy[idx] = 0;
minLazy[idx] = 0;
maxLazy[idx] = 1e9;//*/
}
void RMaxU(int idx, int l, int r, int ql, int qr, int val) {
if (qr < l || ql > r) return;
if (l >= ql && qr >= r) {
maxLazy[idx] = min(maxLazy[idx], val);
minLazy[idx] = min(minLazy[idx], val);
hasLazy[idx] = 1;
return;
}
push(idx, l, r);
int mid = (l + r) >> 1;
if (l != r) {
RMaxU(idx*2, l, mid, ql, qr, val);
RMaxU(idx*2+1, mid + 1, r, ql, qr, val);
}//*/
}
void RMinU(int idx, int l, int r, int ql, int qr, int val) {
if (qr < l || ql > r) return;
if (l >= ql && qr >= r) {
maxLazy[idx] = max(maxLazy[idx], val);
minLazy[idx] = max(minLazy[idx], val);
hasLazy[idx] = 1;
return;
}
push(idx, l, r);
int mid = (l + r) >> 1;
if (l != r) {
RMinU(idx*2, l, mid, ql, qr, val);
RMinU(idx*2+1, mid + 1, r, ql, qr, val);
}//*/
}
int query(int idx, int l, int r, int k) {
push(idx, l, r);
if (l == r) {
return tree[0][idx];
}
int mid = (l + r) >> 1;
if (k <= mid) {
return query(idx*2, l, mid, k);
} else {
return query(idx*2+1, mid + 1, r, k);
}
return 0;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegmentTree seg;
seg.build(n, 1, 0, n - 1);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
seg.RMinU(1, 0, n-1, left[i], right[i], height[i]);
} else {
seg.RMaxU(1, 0, n-1, left[i], right[i], height[i]);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = seg.query(1, 0, n - 1, i);
}
}
/*
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;
}*/
/*
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
*/
