#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define fls cout.flush()
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using mii = map<int,int>;
using lld = long double;
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
const int mod = 1e9+7;
bool umax(int &a, int b){if(b >a){a = b; return 1;} return 0;}
bool umin(int &a, int b){if(b <a){a = b; return 1;} return 0;}
struct node{int mn,mx,pr;};
node st[8000008];
void pro(int nodo,int l, int r ){
if(st[nodo].pr == 0 || l == r) return;
int mid =(l+r)/2;st[nodo].pr = 0;
umax(st[nodo*2].mn, st[nodo].mn);umin(st[nodo*2].mn,st[nodo].mx);
umin(st[nodo*2].mx, st[nodo].mx);umax(st[nodo*2].mx,st[nodo].mn);
umax(st[nodo*2+1].mn, st[nodo].mn);umin(st[nodo*2+1].mn,st[nodo].mx);
umin(st[nodo*2+1].mx, st[nodo].mx);umax(st[nodo*2+1].mx,st[nodo].mn);
st[nodo*2].pr = -1;st[nodo*2+1].pr = -1;
}
void update(int nodo, int l, int r , int i, int j, int op, int val){
pro(nodo,l,r);
// cout << nodo << " " << l << " " << r << endl;
if(i > r || j < l)return;
if(l >= i and r <= j){// rango completo
if(op==1){
umax(st[nodo].mn, val); umax(st[nodo].mx, val);
}else{
umin(st[nodo].mn, val); umin(st[nodo].mx, val);
}
st[nodo].pr = -1;
pro(nodo,l,r);return;
}
update(nodo*2,l,(l+r)/2,i,j,op,val);
update(nodo*2+1,(l+r)/2 +1, r, i,j,op,val);
st[nodo].mn = min(st[nodo*2].mn , st[nodo*2+1].mn);
st[nodo].mx = max(st[nodo*2].mx , st[nodo*2+1].mx);
}
int query(int nodo, int l, int r, int idx){
pro(nodo,l,r);
if(l == r)return st[nodo].mn;
int mid = (l+r)/2;
if(idx <= mid) return query(nodo*2,l,mid,idx);
return query(nodo*2+1,mid+1,r,idx);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0; i<k; i++){
if (op[i] == 1) update(1,0,n-1,left[i], right[i], 1, height[i]);
else update(1,0,n-1,left[i], right[i], 0, height[i]);
}
for(int i = 0; i < n; i++)
finalHeight[i] = query(1,0,n-1, i);
return;
}
