#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
// #define int long long
#define lowbit(x) x&-x
#define ckmax(a, b) a = max(a, b)
const int maxn = 1e6 + 5;
const int N = 998244353;
const int INF = 1e9;
vector<vector<int>> g;
int r[maxn], c[maxn];
int n, m, nm;
pll st[maxn * 4];
int tag[maxn * 4];
void build(int v = 1, int l = 0, int r = nm - 1){
st[v] = {0, r - l + 1};
if(l == r) return;
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
}
void cast(int v, int val){
tag[v] += val, st[v].f += val;
}
void push(int v){
if(tag[v]){
cast(v * 2, tag[v]);
cast(v * 2 + 1, tag[v]);
tag[v] = 0;
}
}
pll op(pll a, pll b){
if(a.f != b.f) return a.f < b.f ? a : b;
return {a.f, a.s + b.s};
}
void upd(int l, int r, int val, int v = 1, int L = 0, int R = nm - 1){
if(v == 1) cout<<"upd : "<<l<<" "<<r<<" "<<val<<"\n";
if(l > R || r < L) return;
if(l <= L && r >= R){
cast(v, val);
return;
}
push(v);
int m = (L + R) / 2;
upd(l, r, val, v * 2, L, m);
upd(l, r, val, v * 2 + 1, m + 1, R);
st[v] = op(st[v * 2], st[v * 2 + 1]);
}
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool inbound(int x, int y){ return x >= 0 && y >= 0 && x <= n + 1 && y <= m + 1;}
void chg(int i, int j, int val){
int mn = INF;
for(int d = 0; d < 4; d++){
int x = i + dx[d], y = j + dy[d];
if(!inbound(x, y)) continue;
mn = min(mn, g[x][y]);
}
if(mn > g[i][j] && g[i][j]) upd(g[i][j], mn - 1, val);
}
void box(int i, int j, int val){
vector<int> c({g[i - 1][j - 1], g[i - 1][j], g[i][j - 1], g[i][j]});
sort(c.begin(), c.end());
upd(c[0], c[1] - 1, val);
upd(c[2], c[3] - 1, val);
}
void give_initial_chart(int n, int m, vector<int> R, vector<int> C){
g = vector<vector<int>>(n + 2, vector<int>(m + 2, n * m + 1));
::n = n, ::m = m, nm = n * m;
build();
for(int i = 0; i < n * m; i++) r[i] = ++R[i], c[i] = ++C[i], g[r[i]][c[i]] = i;
for(int i = 1; i <= n + 1; i++){
for(int j = 1; j <= m + 1; j++){
box(i, j, 1);
}
}
}
void get(int x, int y, vector<pll> &a){
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
if(inbound(x + i, y + j) && x + i && y + j) a.pb({x + i, y + j});
}
}
a.pb({x, y});
}
void sort_unique(vector<pll> &a){
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
}
ostream &operator<<(ostream &s, pll &p){
s << "["<<p.f<<", "<<p.s<<"] ";
return s;
}
int swap_seats(int a, int b){
int x1 = r[a], y1 = c[a], x2 = r[b], y2 = c[b];
vector<pll> pt, pt2;
get(x1, y1, pt), get(x2, y2, pt);
sort_unique(pt);
for(auto [x, y] : pt) box(x, y, -1);
r[a] = x2, c[a] = y2, r[b] = x1, c[b] = y1;
swap(g[x1][y1], g[x2][y2]);
for(auto [x, y] : pt) box(x, y, 1);
if(st[1].f > 4) return 0;
return st[1].s;
}
// signed main(void){
// fastio;
// }
