#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 2e6 + 10;
const int MAXQ = 5e5 + 10;
const int MAXH = 1e5 + 10;
const int INF = 1e9 + 10;
struct SegmentTree
{
struct node
{
int lazy;
int minel;
int maxel;
node()
{
lazy = INF;
minel = 0;
maxel = 0;
}
node(int x)
{
minel = maxel = x;
}
};
node tree[4 * MAXN];
int h[MAXN];
int n;
SegmentTree()
{
n = 0;
}
void push_lazy(int left, int right, int idx)
{
if(tree[idx].lazy == INF)
return;
tree[idx].minel = tree[idx].maxel = tree[idx].lazy;
if(left != right)
{
tree[2 * idx].lazy = tree[2 * idx + 1].lazy = tree[idx].lazy;
}
tree[idx].lazy = INF;
}
void update_max(int left, int right, int idx, int qleft, int qright, int val)
{
push_lazy(left, right, idx);
if(qright < left || right < qleft)
return;
if(tree[idx].minel >= val)
return;
if(qleft <= left && right <= qright && tree[idx].maxel <= val)
{
tree[idx].lazy = val;
push_lazy(left, right, idx);
return;
}
int mid = left + (right - left) / 2;
update_max(left, mid, 2 * idx, qleft, qright, val);
update_max(mid + 1, right, 2 * idx + 1, qleft, qright, val);
tree[idx].minel = min(tree[2 * idx].minel, tree[2 * idx + 1].minel);
tree[idx].maxel = max(tree[2 * idx].maxel, tree[2 * idx + 1].maxel);
}
void update_min(int left, int right, int idx, int qleft, int qright, int val)
{
push_lazy(left, right, idx);
if(qright < left || right < qleft)
return;
if(tree[idx].maxel <= val)
return;
if(qleft <= left && right <= qright && tree[idx].minel >= val)
{
tree[idx].lazy = val;
push_lazy(left, right, idx);
return;
}
int mid = left + (right - left) / 2;
update_min(left, mid, 2 * idx, qleft, qright, val);
update_min(mid + 1, right, 2 * idx + 1, qleft, qright, val);
tree[idx].minel = min(tree[2 * idx].minel, tree[2 * idx + 1].minel);
tree[idx].maxel = max(tree[2 * idx].maxel, tree[2 * idx + 1].maxel);
}
void build(int left, int right, int idx)
{
push_lazy(left, right, idx);
if(left == right)
{
h[left] = tree[idx].minel;
return;
}
int mid = left + (right - left) / 2;
build(left, mid, 2 * idx);
build(mid + 1, right, 2 * idx + 1);
}
void update_max(int left, int right, int val)
{
update_max(1, n, 1, left, right, val);
}
void update_min(int left, int right, int val)
{
update_min(1, n, 1, left, right, val);
}
void build()
{
build(1, n, 1);
}
void query(int type, int left, int right, int val)
{
if(type == 1)
update_max(left, right, val);
else if(type == 2)
update_min(left, right, val);
else
assert(false);
}
int access(int idx)
{
return h[idx + 1];
}
};
SegmentTree st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
st.n = n;
for(int i = 0; i < k; i++)
{
st.query(op[i], left[i] + 1, right[i] + 1, height[i]);
}
st.build();
for(int i = 0; i < n; i++)
{
finalHeight[i] = st.access(i);
}
}
// int op[MAXN];
// int l[MAXN];
// int r[MAXN];
// int height[MAXN];
// int finalHeight[MAXN];
// int n, k;
// int main()
// {
// cin >> n >> k;
// for(int i = 0; i < k; i++)
// {
// cin >> op[i] >> l[i] >> r[i] >> height[i];
// }
// buildWall(n, k, op, l, r, height, finalHeight);
// for(int i = 0; i < n; i++)
// {
// cout << finalHeight[i] << " ";
// }
// cout << endl;
// return 0;
// }
