#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;

const int N=2000007,pot=1<<19;

int L[2*pot+7];
int R[2*pot+7];
vector<pair<pair<int,int>,int>>Q[N];

void ins(int v,int l,int r)
{
	v+=pot-1;
	L[v]=l;
	R[v]=r;
	while(v>1)
	{
		v/=2;
		L[v]=max(L[2*v],L[2*v+1]);
		R[v]=min(R[2*v],R[2*v+1]);
	}
}

int getL(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return L[v];
	if(r<a||l>b) return 0;
	return max(getL(2*v,a,b,l,(l+r)/2),getL(2*v+1,a,b,(l+r)/2+1,r)); 
}
int getR(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return R[v];
	if(r<a||l>b) return 100000;
	return min(getR(2*v,a,b,l,(l+r)/2),getR(2*v+1,a,b,(l+r)/2+1,r)); 
}

void buildWall(int n,int q,int op[],int lx[],int rx[],int h[],int ans[])
{
	FOR(i,0,q-1)
	{
		if(op[i]==1) Q[lx[i]].pb({{h[i],100000},i+1});
		else Q[lx[i]].pb({{0,h[i]},i+1});
		Q[rx[i]+1].pb({{0,100000},i+1});
	}
	FOR(i,1,2*pot) R[i]=100000;
	FOR(i,0,n-1)
	{
		for(auto [p,j]:Q[i]) ins(j,p.st,p.nd);
		int l=1,r=q,sr,t=-1;
		while(l<=r)
		{
			sr=(l+r)/2;
			int la=getL(1,sr,q,1,pot);
			int ra=getR(1,sr,q,1,pot);
			if(la>ra)
			{
				t=sr;
				l=sr+1;
			}
			else r=sr-1;
		}
		debug(t);
		if(t==-1) ans[i]=getL(1,1,q,1,pot);
		else if(op[t-1]==1) ans[i]=getR(1,t+1,q,1,pot);
		else ans[i]=getL(1,t+1,q,1,pot);
	}
	return ;
}