#include <bits/stdc++.h>
struct Seg {
int size;
std::vector <int> res, min, laz;
Seg(int s) {
size = 1;
while (size < s) {
size <<= 1;
}
res.resize(size << 1, 0);
min.resize(size << 1, 0);
laz.resize(size << 1, 0);
size = s;
build(0, 0, size);
}
void build(int now, int l, int r) {
if (!(r - l - 1)) {
res[now] = 1;
return;
}
int mid = (l + r) >> 1;
build(now * 2 + 1, l, mid);
build(now * 2 + 2, mid, r);
res[now] = res[now * 2 + 1] + res[now * 2 + 2];
}
void push(int now, int l, int r) {
min[now] += laz[now];
if (r - l - 1) {
laz[now * 2 + 1] += laz[now];
laz[now * 2 + 2] += laz[now];
}
laz[now] = 0;
}
void update(int l, int r, int val) {
if (r <= l) {
return;
}
update(l, r, val, 0, 0, size);
}
void update(int tl, int tr, int val, int now, int l, int r) {
if (l >= tr || r <= tl) {
return;
}
push(now, l, r);
if (l >= tl && r <= tr) {
laz[now] += val;
return;
}
int mid = (l + r) >> 1;
update(tl, tr, val, now * 2 + 1, l, mid);
update(tl, tr, val, now * 2 + 2, mid, r);
push(now * 2 + 1, l, mid);
push(now * 2 + 2, mid, r);
min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
res[now] =
res[now * 2 + 1] * (min[now * 2 + 1] == min[now]) +
res[now * 2 + 2] * (min[now * 2 + 2] == min[now]);
}
int query() {
push(0, 0, size);
return res[0] * (min[0] == 4);
}
} seg(1);
int n, m;
std::vector <std::vector <int>> g;
std::vector <std::pair <int, int>> inv;
void fix(int i, int j, int val) {
std::vector <int> vals;
for (int di = 0; di <= 1; di++) {
for (int dj = 0; dj <= 1; dj++) {
vals.push_back(g[i + di][j + dj]);
}
}
std::sort(vals.begin(), vals.end());
seg.update(vals[0], vals[1], val);
seg.update(vals[2], vals[3], val);
}
void give_initial_chart(int h, int w, std::vector <int> r, std::vector <int> c) {
n = h;
m = w;
seg = Seg(n * m);
g = std::vector <std::vector <int>> (n + 2, std::vector <int> (m + 2, n * m));
inv = std::vector <std::pair <int, int>> (h * w);
for (int i = 0; i < n * m; i++) {
inv[i] = { ++r[i], ++c[i] };
g[r[i]][c[i]] = i;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
fix(i, j, 1);
}
}
}
int swap_seats(int a, int b) {
auto av = inv[a];
auto bv = inv[b];
for (int di = 0; di <= 1; di++) {
for (int dj = 0; dj <= 1; dj++) {
fix(av.first - di, av.second - dj, -1);
fix(bv.first - di, bv.second - dj, -1);
}
}
std::swap(g[av.first][av.second], g[bv.first][bv.second]);
std::swap(inv[a], inv[b]);
for (int di = 0; di <= 1; di++) {
for (int dj = 0; dj <= 1; dj++) {
fix(av.first - di, av.second - dj, 1);
fix(bv.first - di, bv.second - dj, 1);
}
}
return seg.query();
}
