#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define ll long long
#define mp make_pair
const int N = 5e5 + 10;
ll K;
struct seg {
ll t[4 * N] = {0};
ll t2[4 * N] = {0};
void upd1(ll p, ll z, ll v = 1, ll tl = 0, ll tr = K) {
if(tl == tr) {
t[v] = z;
return;
}
ll m = (tl + tr) >> 1ll;
if(p <= m)upd1(p, z, v * 2, tl, m);
else upd1(p, z, v * 2 + 1, m + 1, tr);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void upd2(ll p, ll z, ll v = 1, ll tl = 0, ll tr = K) {
if(tl == tr) {
t2[v] = z;
return;
}
ll m = (tl + tr) >> 1ll;
if(p <= m)upd2(p, z, v * 2, tl, m);
else upd2(p, z, v * 2 + 1, m + 1, tr);
t2[v] = min(t2[v * 2], t2[v * 2 + 1]);
}
ll get2(ll p, ll v = 1, ll tl = 0, ll tr = K) {
if(tl == tr) {
return t[v];
}
ll m = (tl + tr) >> 1ll;
if(p <= m)
return max(get2(p, v * 2, tl, m), t[v * 2 + 1]);
return get2(p, v * 2 + 1, m + 1, tr);
}
ll get3(ll p, ll v = 1, ll tl = 0, ll tr = K) {
if(tl == tr) {
return t2[v];
}
ll m = (tl + tr) >> 1ll;
if(p <= m)
return min(get3(p, v * 2, tl, m), t2[v * 2 + 1]);
return get3(p, v * 2 + 1, m + 1, tr);
}
ll get(ll x, ll y, ll v = 1, ll tl = 0, ll tr = K) {
if(tl == tr) {
return tl;
}
ll m = (tl + tr) >> 1ll;
ll a = max(x, t[v * 2 + 1]);
ll b = min(y, t2[v * 2 + 1]);
if(a > b)
return get(x, y, v * 2 + 1, m + 1, tr);
return get(a, b, v * 2, tl, m);
}
} rt;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector<int> g[n + 1];
K = k;
rt.upd1(0, 1e9);
rt.upd2(0, 0);
for(int i = 0; i < k; i++) {
g[left[i]].pb(i);
g[right[i] + 1].pb(i);
rt.upd2(i + 1, 1e9);
rt.upd1(i + 1, 0);
}
ll cnt = 0;
for(int i = 0; i < n; i++) {
for(auto u : g[i]) {
if(left[u] == i) {
if(op[u] == 1) rt.upd1(u + 1, height[u]);
if(op[u] == 2) rt.upd2(u + 1, height[u]);
} else {
if(op[u] == 1) rt.upd1(u + 1, 0);
if(op[u] == 2) rt.upd2(u + 1, 1e9);
}
}
//if(i == 3)cout << "________________________";
// cout << "here " << i << " : ";
ll pos = rt.get(0, 1e9);
ll xs = rt.get2(pos), ys = rt.get3(pos);
ll xe = rt.get2(pos + 1), ye = rt.get3(pos + 1);
// cout << pos << "\n";
// cout << xs << " " << ys << "\n";
// cout << xe << " " << ye << "\n";
if(pos == 0) finalHeight[i] = xe;
if(xe == xs) finalHeight[i] = xe;
if(ye == ys) finalHeight[i] = ye;
//ll y = rt.get3(pos);
//if(finalHeight[i] == 1e9)final
//if(i == 3)cout << "________________________";
}
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;
}
/*
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
*/
