#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define lc(v) (v * 2)
#define rc(v) (v * 2 + 1)
#define mid (l + r) / 2
#define ff first
#define ss second
const int N = 1e6;
class seg_tree {
pair<int, int> *t;
int n;
void build(int v, int l, int r, pair<int, int> a[]) {
for (int i = 0; i < n; i++)
t[n + i] = {a[i].ss, a[i].ff};
for (int i = n - 1; i >= 1; i--)
t[i] = max(t[lc(i)], t[rc(i)]);
}
public:
seg_tree(int n, pair<int, int> a[]) {
this->n = n;
t = new pair<int, int>[n * 2];
build(1, 0, n - 1, a);
}
pair<int, int> query(int l, int r) {
l += n;
r += n;
pair<int, int> mi = {-1, -1};
while (l < r) {
if (l & 1)
mi = max(mi, t[l]), l++;
if (r & 1)
r--, mi = max(mi, t[r]);
l /= 2, r /= 2;
}
return mi;
}
void update(int pos) {
pos += n;
t[pos] = {-1, -1};
while (pos > 1) {
pos >>= 1;
t[pos] = max(t[lc(pos)], t[rc(pos)]);
}
}
};
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
pair<int, int> t1[T], t2[T];
priority_queue<int, vector<int>, decltype(greater<>())> x, y, x_, y_;
for (int i = 0; i < T; i++) {
t1[i] = {W[i], S[i]};
t2[i] = {S[i], W[i]};
x.push(W[i]);
y.push(S[i]);
}
sort(t1, t1 + T);
sort(t2, t2 + T);
sort(X, X + A);
sort(Y, Y + B);
if ((t1[T - 1].ff >= X[A - 1] && t1[T - 1].ss >= Y[B - 1]) ||
(t2[T - 1].ff >= Y[B - 1] && t2[T - 1].ss >= X[A - 1]))
return -1;
seg_tree st1(T, t1), st2(T, t2);
int ans = 0, done = 0;
while (done != T) {
ans++;
int p = upper_bound(X, X + A, x.top()) - X;
while (p != A && done != T) {
pair<int, int> q = st1.query(0, lower_bound(t1, t1 + T, pair<int, int>{X[p] - 1, 1e9}) - t1);
int ind = upper_bound(t1, t1 + T, pair<int, int>{q.ss, q.ff}) - t1 - 1;
t1[ind].ss = 1e9 + 7;
st1.update(ind);
x_.push(q.ss);
ind = upper_bound(t2, t2 + T, q) - t2 - 1;
t2[ind].ss = 1e9 + 7;
st2.update(ind);
y_.push(q.ff);
while (!x_.empty() && x.top() == x_.top())
x.pop(), x_.pop();
while (!y_.empty() && y.top() == y_.top())
y.pop(), y_.pop();
done++;
int p_ = upper_bound(X, X + A, x.top()) - X;
p = max(p + 1, p_);
}
p = upper_bound(Y, Y + B, y.top()) - Y;
while (p != B && done != T) {
pair<int, int> q = st2.query(0, lower_bound(t2, t2 + T, pair<int, int>{Y[p] - 1, 1e9}) - t2);
int ind = upper_bound(t2, t2 + T, pair<int, int>{q.ss, q.ff}) - t2 - 1;
t2[ind].ss = 2e9 + 7;
st2.update(ind);
y_.push(q.ss);
ind = upper_bound(t1, t1 + T, q) - t1 - 1;
t1[ind].ss = 2e9 + 7;
st1.update(ind);
x_.push(q.ff);
while (!x_.empty() && x.top() == x_.top())
x.pop(), x_.pop();
while (!y_.empty() && y.top() == y_.top())
y.pop(), y_.pop();
done++;
int p_ = upper_bound(Y, Y + B, y.top()) - Y;
p = max(p + 1, p_);
}
}
return ans;
}
