#include <bits/stdc++.h>
using namespace std;
int N, K, Q;
struct Node
{
int l, r;
}ST[8000001];
inline void Setup()
{
K = 1;
while(K < N) K <<= 1;
for(int i = 1; i <= (N + K - 1); i++) {ST[i].l = 0; ST[i].r = 0;}
return;
}
inline void Merge(int i)
{
ST[i].l = min(ST[i << 1].l, ST[i << 1 | 1].l);
ST[i].r = max(ST[i << 1].r, ST[i << 1 | 1].r);
return;
}
inline void Propagate(int i)
{
if(i >= K) return;
ST[i << 1].l = max(ST[i].l, ST[i << 1].l);
ST[i << 1].r = min(ST[i].r, ST[i << 1].r);
if(ST[i << 1].l > ST[i << 1].r)
{
if((ST[i].l <= ST[i << 1].l) && (ST[i << 1].l <= ST[i].r)) ST[i << 1].r = ST[i << 1].l;
else ST[i << 1].l = ST[i << 1].r;
}
ST[i << 1 | 1].l = max(ST[i].l, ST[i << 1 | 1].l);
ST[i << 1 | 1].r = min(ST[i].r, ST[i << 1 | 1].r);
if(ST[i << 1 | 1].l > ST[i << 1 | 1].r)
{
if((ST[i].l <= ST[i << 1 | 1].l) && (ST[i << 1 | 1].l <= ST[i].r)) ST[i << 1 | 1].r = ST[i << 1 | 1].l;
else ST[i << 1 | 1].l = ST[i << 1 | 1].r;
}
return;
}
inline void Finish()
{
for(int i = 1; i < K; i++) Propagate(i);
return;
}
inline void Update(int L, int R, int T, int X, int i = 1, int LC = 1, int RC = K)
{
Propagate(i);
if((LC > R) || (L > RC)) return;
if((L <= LC) && (RC <= R))
{
if(T == 1) {ST[i].l = max(X, ST[i].l); ST[i].r = max(X, ST[i].r);}
if(T == 2) {ST[i].l = min(X, ST[i].l); ST[i].r = min(X, ST[i].r);}
Propagate(i);
return;
}
int S = (LC + RC) >> 1;
Update(L, R, T, X, i << 1, LC, S);
Update(L, R, T, X, i << 1 | 1, S + 1, RC);
Merge(i);
return;
}
void buildWall(int n, int q, int t[], int l[], int r[], int x[], int O[])
{
N = n;
Q = q;
Setup();
for(int i = 0; i < Q; i++) Update(l[i] + 1, r[i] + 1, t[i], x[i]);
Finish();
for(int i = 0; i < N; i++) O[i] = ST[i + K].l;
return;
}
//int main()
//{
// int n, q;
// cin >> n >> q;
// int t[q], l[q], r[q], x[q], o[n];
// for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i] >> x[i];
// buildWall(n, q, t, l, r, x, o);
// for(int i = 0; i < n; i++) cout << o[i] << " \n"[i == (n - 1)];
// return 0;
//}
