#include "wall.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
const int N = 2e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
mt19937 rng(time(nullptr));
int n, k, Mn[N << 2], Mx[N << 2], lz[N << 2];
void S(int v, int tl, int tr)
{
if(lz[v] == -1 || tl == tr) return;
Mn[v << 1] = Mx[v << 1] = Mn[v << 1 | 1] = Mx[v << 1 | 1] = lz[v << 1] = lz[v << 1 | 1] = lz[v];
lz[v] = -1;
}
void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = n - 1) /// baraye min
{
S(v, tl, tr);
if(l > tr || r < tl || Mx[v] <= x) return;
if(l <= tl && tr <= r && Mn[v] == Mx[v])
{
Mx[v] = Mn[v] = lz[v] = x;
return;
}
int mid = (tl + tr) >> 1;
upd(l, r, x, v << 1, tl, mid), upd(l, r, x, v << 1 | 1, mid + 1, tr);
Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]);
Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]);
}
void UPD(int l, int r, int x, int v = 1, int tl = 0, int tr = n - 1)
{
S(v, tl, tr);
if(l > tr || r < tl || Mn[v] >= x) return;
if(l <= tl && tr <= r && Mx[v] == Mn[v])
{
Mn[v] = Mx[v] = lz[v] = x;
return;
}
int mid = (tl + tr) >> 1;
UPD(l, r, x, v << 1, tl, mid), UPD(l, r, x, v << 1 | 1, mid + 1, tr);
Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]);
Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]);
}
int get(int p, int v = 1, int tl = 0, int tr = n - 1)
{
S(v, tl, tr);
if(tl == tr) return Mx[v];
int mid = (tl + tr) >> 1;
if(p <= mid) return get(p, v << 1, tl, mid);
else return get(p, v << 1 | 1, mid + 1, tr);
}
void buildWall(int _n, int _k, int op[], int left[], int right[], int height[], int finalHeight[])
{
n = _n;
k = _k;
for(int i = 0; i < k; i ++)
{
if(op[i] == 1)
{
UPD(left[i], right[i], height[i]);
}
else
{
upd(left[i], right[i], height[i]);
}
}
for(int i = 0; i < n; i ++)
{
finalHeight[i] = get(i);
}
}
