#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"
const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;
int n, m, q;
int x[maxn];
int y[maxn];
vector<int> f[maxn];
int d[maxn * 4];
int c[maxn * 4];
int t[maxn * 4];
void build(int v = 1, int tl = 1, int tr = n * m){
d[v] = 0; c[v] = tr - tl + 1;
if(tl < tr){
int mid = (tl + tr) >> 1;
build(v<<1, tl, mid);
build(v<<1|1, mid+1, tr);
}
} void pre(int v, int x){
d[v] += x;
t[v] += x;
} void push(int v, int tl, int tr){
if(tl == tr) return;
pre(v<<1, t[v]);
pre(v<<1|1, t[v]);
t[v] = 0;
} void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = n * m){
if(tl > r || tr < l) return;
if(l <= tl && tr <= r) pre(v, x);
else{
push(v, tl, tr);
int mid = (tl + tr) >> 1;
upd(l, r, x, v<<1, tl, mid);
upd(l, r, x, v<<1|1, mid+1, tr);
if(d[v<<1] == d[v<<1|1]){
d[v] = d[v<<1];
c[v] = c[v<<1] + c[v<<1|1];
} else{
d[v] = min(d[v<<1], d[v<<1|1]);
if(d[v<<1] == d[v]) c[v] = c[v<<1];
else c[v] = c[v<<1|1];
}
}
} void out(int v = 1, int tl = 1, int tr = n * m){
push(v, tl, tr);
if(tl == tr) cout << d[v] << ' ';
else{
int mid = (tl + tr) >> 1;
out(v<<1, tl, mid);
out(v<<1|1, mid+1, tr);
}
}
vector<int> v;
void calc(int i, int j, int x){
v = {f[i][j], f[i+1][j], f[i][j+1], f[i+1][j+1]};
sort(v.begin(), v.end());
upd(v[0], v[1] - 1, x);
upd(v[2], v[3] - 1, x);
} void updCell(int i, int j, int c){
for(int x = i-1; x <= i; x++){
for(int y = j-1; y <= j; y++){
calc(x, y, c);
}
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
n = H, m = W;
for(int i = 0; i <= n + 1; i++){
f[i] = vector<int>(m + 2, inf);
} for(int i = 0; i < n * m; i++){
R[i]++; C[i]++;
x[i+1] = R[i]; y[i+1] = C[i];
f[R[i]][C[i]] = i + 1;
} build();
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++){
calc(i, j, 1);
}
}
}
int swap_seats(int a, int b){
a++; b++;
updCell(x[a], y[a], -1);
f[x[a]][y[a]] = b;
updCell(x[a], y[a], 1);
updCell(x[b], y[b], -1);
f[x[b]][y[b]] = a;
updCell(x[b], y[b], 1);
swap(x[a], x[b]); swap(y[a], y[b]);
return (d[1] == 4) * c[1];
}
