#include <bits/stdc++.h>
using namespace std;
struct LazySegmentTree {
int n;
vector<int>dat,lazy;
LazySegmentTree(int N) {
n = 1;
while(n < N) {
n *= 2;
}
dat.resize(2*n,-1);
lazy.resize(2*n,-1);
}
void eval(int k) {
if(lazy[k] == -1) return;
if(k < n) {
lazy[k*2] = max(lazy[k*2],lazy[k]);
lazy[k*2+1] = max(lazy[k*2+1],lazy[k]);
}
dat[k] = max(dat[k],lazy[k]);
lazy[k] = -1;
}
void update_sub(int a,int b,int l,int r,int k,int x) {
if(b <= l || r <= a) {
return;
}
if(a <= l && r <= b) {
lazy[k] = max(lazy[k],x);
return;
}
update_sub(a,b,l,(l+r)/2,k*2,x);
update_sub(a,b,(l+r)/2,r,k*2+1,x);
}
void update(int l,int r,int x) {
update_sub(l,r,0,n,1,x);
}
int query(int x) {
int ans = 0,now = x+n;
while(now > 0) {
ans = max(ans,lazy[now]);
now /= 2;
}
return ans;
}
};
void buildWall(int n, int k, int op[], int left[],int right[],int height[], int finalHeight[]) {
int MAX = 0;
for(int i = 0; i < k; i++) {
MAX = max(MAX,height[i]);
}
vector<int>l(n,0),r(n,MAX+1);
vector<array<int,3>>tmp1,tmp2;
for(int i = 0; i < k; i++) {
if(op[i] == 1) {
tmp1.push_back({height[i],1,i});
}
else {
tmp2.push_back({height[i],1,i});
}
}
while(true) {
bool f = false;
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) f = true;
}
if(!f) break;
vector<array<int,3>>q1 = tmp1,q2 = tmp2;
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) {
int mid = (l[i]+r[i])/2;
q1.push_back({mid,0,i});
q2.push_back({mid,0,i});
}
}
sort(q1.rbegin(),q1.rend());
sort(q2.begin(),q2.end());
vector<int>mx1(n),mx2(n);
LazySegmentTree s1(n),s2(n);
{
for(int i = 0; i < q1.size(); i++) {
if(q1[i][1] == 1) {
int id = q1[i][2];
s1.update(left[id],right[id]+1,id);
}
else {
mx1[q1[i][2]] = s1.query(q1[i][2]);
}
}
}
{
for(int i = 0; i < q2.size(); i++) {
if(q2[i][1] == 1) {
int id = q2[i][2];
s2.update(left[id],right[id]+1,id);
}
else {
mx2[q2[i][2]] = s2.query(q2[i][2]);
}
}
}
for(int i = 0; i < n; i++) {
if(l[i]+1 < r[i]) {
int mid = (l[i]+r[i])/2;
if(mx2[i] < mx1[i]) {
l[i] = mid;
}
else {
r[i] = mid;
}
}
}
}
for(int i = 0; i < n; i++) {
finalHeight[i] = l[i];
}
}
