#include <bits/stdc++.h>
//#include <"wall.h">
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 2001000
#define pa pair<ll, ll>
#define ld long double
ll tr[2 * mn], kdaj[2 * mn];
ll get(ll pos){
pos+=mn;
ll ret=1,last=-1;
for(;pos;pos>>=1){
if(kdaj[pos]>last) last=kdaj[pos], ret=tr[pos];
}
return ret-1;
}
void upd(ll l, ll r, ll val, ll t){
l+=mn, r+=mn;
for(;l<r;l>>=1, r>>=1){
if(l&1){
if(val<0){ if(-val<tr[l]) tr[l]=-val;kdaj[l]=t;}
else{if(val>tr[l]) tr[l]=val;kdaj[l]=t;}
l++;
}
if(r&1){
--r;
if(val<0){ if(-val<tr[r]) tr[r]=-val;kdaj[r]=t;}
else{if(val>tr[r]) tr[r]=val;kdaj[r]=t;}
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
loop(i, 0, 2 * mn) tr[i]=1, kdaj[i]=-1;
loop(i, 0, k) upd(left[i], right[i]+1, (op[i]) * (height[i]+1), i);
loop(i, 0, n) finalHeight[i]=get(i);
// dej minus 1
}
