#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"
//#define HOME
/**
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
**/
#ifndef HOME
#include "wall.h"
#endif // HOME
const int ADD = 1, REMOVE = 2;
struct node_t {
int low;
int high;
};
struct event_t {
int pos;
node_t value;
};
node_t join (node_t left_node, node_t right_node) {
return {max (left_node.low, right_node.low), min (left_node.high, right_node.high)};
}
const int MX = 1e5;
struct segment_tree {
vector <node_t> seg;
segment_tree (int n) {
seg.resize (1 + 4 * n, {0, MX});
}
void update (int node, int lb, int rb, int pos, node_t value) {
if (lb == rb) {
seg[node] = value;
return;
}
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
if (pos <= mid)
update (left_node, lb, mid, pos, value);
else
update (right_node, mid + 1, rb, pos, value);
seg[node] = join (seg[left_node], seg[right_node]);
}
int query (int node, int lb, int rb, node_t &cur) {
if (lb == rb)
return lb;
int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
node_t take = join (cur, seg[right_node]);
if (take.low <= take.high) {
cur = take;
return query (left_node, lb, mid, cur);
}
else {
return query (right_node, mid + 1, rb, cur);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector <vector <event_t>> events (1 + n);
for (int i = 0; i < k; i++) {
if (op[i] == ADD)
events[left[i]].push_back ({i, {height[i], MX}});
else
events[left[i]].push_back ({i, {0, height[i]}});
events[right[i] + 1].push_back ({i, {0, MX}});
}
vector <node_t> h (k);
segment_tree aint (k);
int ans = 0;
for (int i = 0; i < n; i++) {
for (event_t event : events[i]) {
aint.update (1, 0, k - 1, event.pos, event.value);
h[event.pos] = event.value;
}
node_t cur = {0, MX};
int best = aint.query (1, 0, k - 1, cur);
if (join (cur, h[best]).low <= cur.high)
ans = join (cur, h[best]).low;
else if (join (cur, h[best]).low > cur.high)
ans = join (cur, h[best]).high;
else
ans = cur.low;
finalHeight[i] = ans;
}
return;
}
#ifdef HOME
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;
}
#endif // HOME
