#include <bits/stdc++.h>
#include "seats.h"
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : c)
#define ll long long
constexpr bool dbg = false;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
using namespace std;
constexpr int treeBase = 1 << 20, maxn = 1e6 + 7, inf = 5;
int n;
int h, w;
vector<vector<int>> arr;
pair<int, int> location[maxn];
int treeMin[2 * treeBase], treeCnt[2 * treeBase], lazy[2 * treeBase];
static inline void fixNode(int v) {
treeMin[v] = min(treeMin[2 * v] + lazy[2 * v], treeMin[2 * v + 1] + lazy[2 * v + 1]);
treeCnt[v] = 0;
if (treeMin[v] == treeMin[2 * v] + lazy[2 * v]) treeCnt[v] += treeCnt[2 * v];
if (treeMin[v] == treeMin[2 * v + 1] + lazy[2 * v + 1]) treeCnt[v] += treeCnt[2 * v + 1];
}
void initTree() {
rep(i, 0, treeBase) treeMin[i + treeBase] = inf, treeCnt[i + treeBase] = 1;
rep(i, 0, n) treeMin[i + treeBase] = 0;
repD(i, treeBase - 1, -1) fixNode(i);
}
void add(int l, int r, int x) {
DC << "add " << l << ' ' << r << " + " << x << eol;
l += treeBase; r += treeBase;
lazy[l] += x;
if (l != r) lazy[r] += x;
while (l / 2 != r / 2) {
if (l % 2 == 0) lazy[l + 1] += x;
if (r % 2 == 1) lazy[r - 1] += x;
l /= 2; r /= 2;
fixNode(l); fixNode(r);
}
l /= 2; r /= 2;
while (l) fixNode(l), l /= 2;
}
int query() {
return (treeMin[1] == 4 ? treeCnt[1] : 0);
}
void processCorner(int r, int c, bool remove) {
vector<int> v; v.reserve(4);
rep(i, 0, 2) rep(j, 0, 2) v.push_back(arr[r + i][c + j]);
sort(v.begin(), v.end());
add(v[0], v[1] - 1, 1 * (remove ? -1 : 1));
if (v[2] != v[3]) add(v[2], v[3] - 1, inf * (remove ? -1 : 1));
}
void processCorners(int r, int c, bool remove) {
rep(dr, -1, 1) rep(dc, -1, 1) {
if (r + dr < 0 || r + dr + 1 >= h + 2 || c + dc < 0 || c + dc + 1 >= w + 2) continue;
processCorner(r + dr, c + dc, remove);
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h = H, w = W, n = h * w;
initTree();
arr.resize(h + 2); repIn(i, arr) i.resize(w + 2);
rep(i, 0, n) location[i] = {R[i] + 1, C[i] + 1}, arr[R[i] + 1][C[i] + 1] = i;
rep(i, 0, h + 2) arr[i][0] = arr[i][w + 1] = n + 1;
rep(i, 0, w + 2) arr[0][i] = arr[h + 1][i] = n + 1;
rep(i, 0, h + 1) rep(j, 0, w + 1) processCorner(i, j, false);
DC << ' ' << query() << eol;
}
int swap_seats(int a, int b) {
auto& [ra, ca] = location[a];
auto& [rb, cb] = location[b];
processCorners(ra, ca, true), processCorners(rb, cb, true);
swap(ra, rb); swap(ca, cb), swap(arr[ra][ca], arr[rb][cb]);
processCorners(ra, ca, false), processCorners(rb, cb, false);
return query();
}
