#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "robots.h"
const int N = 1 << 16;
const int INF = 1e9;
const pii NO = {-INF, -1};
void build(pii t[]) {
for (int i = N - 1; i > 0; --i) {
t[i] = max(t[i + i], t[i + i + 1]);
}
}
pii query(pii t[], int l, int r) {
pii res = NO;
for (l += N, r += N; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) {
res = max(res, t[l++]);
}
if (r % 2 == 0) {
res = max(res, t[r--]);
}
}
return res;
}
void update(pii t[], int i, pii p) {
t[i += N] = p;
for (i /= 2; i > 0; i /= 2) {
t[i] = max(t[i + i], t[i + i + 1]);
}
}
vector<pii> byx[N], byy[N];
pair<int, int> tx[2 * N], ty[2 * N];
bool used[N];
void iter(int a, int b, int t, int w[], int s[]) {
(void)t;
for (int i = 0; i < a; ++i) {
int j = query(tx, 0, i).y;
while (j >= 0 && used[j]) {
assert(byx[w[j]].size() && byx[w[j]].back().y == j);
byx[w[j]].pop_back();
update(tx, w[j], byx[w[j]].size() ? byx[w[j]].back() : NO);
j = query(tx, 0, i).y;
}
if (j < 0) {
continue;
}
used[j] = true;
}
for (int i = 0; i < b; ++i) {
int j = query(ty, 0, i).y;
while (j >= 0 && used[j]) {
assert(byy[s[j]].size());
assert(byy[s[j]].back().y == j);
byy[s[j]].pop_back();
update(ty, s[j], byy[s[j]].size() ? byy[s[j]].back() : NO);
j = query(ty, 0, i).y;
}
if (j < 0) {
continue;
}
used[j] = true;
}
}
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
sort(x, x + a);
sort(y, y + b);
for (int i = 0; i < t; ++i) {
w[i] = (int)(upper_bound(x, x + a, w[i]) - x);
s[i] = (int)(lower_bound(y, y + b, s[i]) - y);
byx[w[i]].emplace_back(s[i], i);
byy[s[i]].emplace_back(w[i], i);
}
for (int i = 0; i < N; ++i) {
sort(all(byx[i]));
sort(all(byy[i]));
tx[i + N] = byx[i].size() ? byx[i].back() : NO;
ty[i + N] = byy[i].size() ? byy[i].back() : NO;
}
build(tx), build(ty);
int ti = 0;
while (1) {
int was = (int)count(used, used + t, true);
if (was == t) {
break;
}
++ti;
iter(a, b, t, w, s);
int now = (int)count(used, used + t, true);
if (was == now) {
return -1;
}
}
return ti;
}
#ifdef LC
#include "grader.c"
#endif
