#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
struct sgt {
vector<int> t,a; int sz=1,n;
sgt(int _n) {
n=_n;
while (sz<n) sz<<=1;
t.assign(2*sz,n);
a.assign(n+1,-1);
forn(i,n) t[sz-1+i]=i;
}
int merge(int i, int j) {
if (a[i]>a[j]) return i;
else return j;
}
void upd(int v, int l, int r, int i) {
if (r-l==1) return;
int m=(l+r)>>1;
if (i<m) upd(2*v+1,l,m,i);
else upd(2*v+2,m,r,i);
t[v]=merge(t[2*v+1],t[2*v+2]);
}
void set(int i, int x) {
a[i]=x;
upd(0,0,sz,i);
}
int query(int v, int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return n;
if (lx<=l && r<=rx) return t[v];
int m=(l+r)>>1;
int lq=query(2*v+1,l,m,lx,rx);
int rq=query(2*v+2,m,r,lx,rx);
return merge(lq,rq);
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
};
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
sort(x,x+a);
sort(y,y+b);
forn(i,t) {
int z=0;
if (a) z|=w[i]<x[a-1];
if (b) z|=s[i]<y[b-1];
if (!z) return -1;
}
vector<int> pos1(t), pos2(t);
vector<int> un1(t), un2(t);
vector<int> vis(t);
set<pi> s1, s2;
forn(i,t) {
s1.insert({w[i],i});
s2.insert({s[i],i});
}
int m;
m=0;
for(auto&x:s1) pos1[x.s]=m++;
m=0;
for(auto&x:s2) pos2[x.s]=m++;
forn(i,t) un1[pos1[i]]=i;
forn(i,t) un2[pos2[i]]=i;
sgt st1(t), st2(t);
forn(i,t) {
st1.set(pos1[i],s[i]);
st2.set(pos2[i],w[i]);
}
int tot=t;
int ans=0;
while (tot) {
int l=0, r=min(tot,a);
while (l<r) {
int mid=(l+r+1)>>1;
auto it=s1.begin();
int z=1;
for (int i=a-mid; i<a; ++i) {
z&=x[i]>(*it).f;
++it;
}
if (z) l=mid;
else r=mid-1;
}
for (int i=a-r; i<a; ++i) {
auto it=s1.lower_bound({x[i],-1});
if (it==s1.begin()) continue;
it--;
int j=(*it).s;
j=pos1[j];
int j2 = st1.query(0,j+1);
int j3 = un1[j2];
assert(!vis[j3]);
vis[j3]=1;
st1.set(pos1[j3],-2);
st2.set(pos2[j3],-2);
s1.erase({w[j3],j3});
s2.erase({s[j3],j3});
}
tot-=r;
l=0, r=min(tot,b);
while (l<r) {
int mid=(l+r+1)>>1;
auto it=s2.begin();
int z=1;
for (int i=b-mid; i<b; ++i) {
z&=y[i]>(*it).f;
++it;
}
if (z) l=mid;
else r=mid-1;
}
for (int i=b-r; i<b; ++i) {
auto it=s2.lower_bound({y[i],-1});
if (it==s2.begin()) continue;
it--;
int j=(*it).s;
j=pos2[j];
int j2 = st2.query(0,j+1);
int j3 = un2[j2];
assert(!vis[j3]);
vis[j3]=1;
st1.set(pos1[j3],-2);
st2.set(pos2[j3],-2);
s1.erase({w[j3],j3});
s2.erase({s[j3],j3});
}
tot-=r;
++ans;
}
return ans;
}
