#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define fi first
#define se second
#define long long long
using namespace std;
int mn[8000003], mx[8000003];
int lazy[8000003];
void cek_lazy(int pos, int kir, int kan)
{
if(lazy[pos] != -1)
{
mn[pos] = lazy[pos];
mx[pos] = lazy[pos];
if(kan-kir) lazy[pos*2] = lazy[pos*2+1] = lazy[pos];
lazy[pos] = -1;
}
}
void update(int pos, int kir, int kan, int qkir, int qkan, int op, int val)
{
cek_lazy(pos, kir, kan);
// printf("POS : %d %d %d Q : %d %d\n", pos, kir, kan, qkir, qkan);
if(kan < qkir || qkan < kir) return;
if(op == 1 && mn[pos] > val) return;
if(op == 2 && mx[pos] < val) return;
if(op == 1 && mx[pos] <= val && qkir <= kir && kan <= qkan)
{
lazy[pos] = val;
cek_lazy(pos, kir, kan);
return;
}
if(op == 2 && mn[pos] >= val && qkir <= kir && kan <= qkan)
{
lazy[pos] = val;
cek_lazy(pos, kir, kan);
return;
}
if(kir == kan) return;
int mid = (kir+kan)/2;
update(pos*2, kir, mid, qkir, qkan, op, val);
update(pos*2+1, mid+1, kan, qkir, qkan, op, val);
mn[pos] = min(mn[pos*2], mn[pos*2+1]);
mx[pos] = max(mx[pos*2], mx[pos*2+1]);
}
int query(int pos, int kir, int kan, int idx)
{
cek_lazy(pos, kir, kan);
if(kir == idx && kan == idx) return mx[pos];
int mid = (kir+kan)/2;
if(idx <= mid) return query(pos*2, kir, mid, idx);
else return query(pos*2+1, mid+1, kan, idx);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
memset(lazy, -1, sizeof lazy);
for(int i = 0; i < k; i++)
{
// printf("%d %d %d %d\n", op[i], left[i], right[i], height[i]);
update(1, 0, n-1, left[i], right[i], op[i], height[i]);
}
for(int i = 0; i < n; i++)
finalHeight[i] = query(1, 0, n-1, i);
return;
}
