#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
const int N = 1e6 + 5e4 + 5;
int ans = 0;
map<int, int> cmprsx, cmprsy;
multiset<int> curx, cury, curw, curs;
vector<int> used;
struct SegTree{
pair<int, int> tree[N * 4];
multiset<int> st[N * 4];
SegTree(){
for(int i = 0; i < N * 4; i++) st[i].insert(0);
}
void update(int pos, int val, int v = 1, int l = 1, int r = N - 1){
if(l == r) st[v].insert(val), tree[v] = {*prev(st[v].end()), l};
else{
int m = l + (r - l) / 2;
if(pos <= m) update(pos, val, v * 2, l, m);
else update(pos, val, v * 2 + 1, m + 1, r);
tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
}
}
void update2(int pos, int val, int v = 1, int l = 1, int r = N - 1){
if(l == r){
st[v].erase(st[v].find(val));
tree[v] = {*prev(st[v].end()), l};
}
else{
int m = l + (r - l) / 2;
if(pos <= m) update2(pos, val, v * 2, l, m);
else update2(pos, val, v * 2 + 1, m + 1, r);
tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
}
}
pair<int, int> query(int l, int r, int v = 1, int tl = 1, int tr = N - 1){
if(l > r) return {0, 0};
else if(l == tl && r == tr) return tree[v];
else{
int tm = tl + (tr - tl) / 2;
return max(query(l, min(tm, r), v * 2, tl, tm), query(max(l, tm + 1), r, v * 2 + 1, tm + 1, tr));
}
}
};
SegTree wsgt, ssgt;
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]){
for(int i = 0; i < a; i++) cmprsx[x[i]] = 1;
for(int i = 0; i < b; i++) cmprsy[y[i]] = 1;
for(int i = 0; i < t; i++) cmprsx[w[i]] = cmprsy[s[i]] = 1;
int tmp = 0;
for(auto &p : cmprsx) p.second = ++tmp;
tmp = 0;
for(auto &p : cmprsy) p.second = ++tmp;
for(int i = 0; i < a; i++) x[i] = cmprsx[x[i]];
for(int i = 0; i < b; i++) y[i] = cmprsy[y[i]];
for(int i = 0; i < t; i++) w[i] = cmprsx[w[i]], s[i] = cmprsy[s[i]];
sort(x, x + a);
sort(y, y + b);
for(int i = 0; i < a; i++) curx.insert(x[i]);
for(int i = 0; i < b; i++) cury.insert(y[i]);
for(int i = 0; i < t; i++) curw.insert(w[i]), curs.insert(s[i]);
for(int i = 0; i < t; i++) wsgt.update(w[i], s[i]), ssgt.update(s[i], w[i]);
while(curw.size()){
bool flag = false;
ans++;
used.clear();
while(!curw.empty() && !curx.empty()){
int ww = *curw.begin();
auto it = curx.upper_bound(ww);
if(it == curx.end()) break;
int xx = *it;
curx.erase(it);
used.push_back(xx);
pair<int, int> p = wsgt.query(1, xx - 1);
curw.erase(curw.find(p.second));
curs.erase(curs.find(p.first));
wsgt.update2(p.second, p.first);
ssgt.update2(p.first, p.second);
flag = true;
}
for(auto xx : used) curx.insert(xx);
used.clear();
while(!curs.empty() && !cury.empty()){
int ss = *curs.begin();
auto it = cury.upper_bound(ss);
if(it == cury.end()) break;
int yy = *it;
cury.erase(it);
used.push_back(yy);
pair<int, int> p = ssgt.query(1, yy - 1);
curs.erase(curs.find(p.second));
curw.erase(curw.find(p.first));
ssgt.update2(p.second, p.first);
wsgt.update2(p.first, p.second);
flag = true;
}
for(auto yy : used) cury.insert(yy);
if(flag == false) return -1;
}
return ans;
}
