#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false
const int MAXN = 1000 * 1000 + 17;
pii pos[MAXN];
pii st[4 * MAXN]; // min, ile
int lazy[4 * MAXN];
vector<int> a[MAXN];
int h, w;
void szykuj(int i) {
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
st[i * 2].st += lazy[i];
st[i * 2 + 1].st += lazy[i];
lazy[i] = 0;
}
void buduj(int p, int k, int i) {
if (p == k) {
st[i].nd = 1;
return;
}
int sr = (p + k) / 2;
buduj(p, sr, i * 2);
buduj(sr + 1, k, i * 2 + 1);
st[i].nd = st[i * 2].nd + st[i * 2 + 1].nd;
}
void aktualizuj(int p, int k, int a, int b, int w, int i) {
if (k < a || p > b) return;
if (a <= p && k <= b) {
st[i].st += w;
lazy[i] += w;
return;
}
szykuj(i);
int sr = (p + k) / 2;
aktualizuj(p, sr, a, b, w, i * 2);
aktualizuj(sr + 1, k, a, b, w, i * 2 + 1);
if (st[i * 2].st == st[i * 2 + 1].st) {
st[i].st = st[i * 2].st;
st[i].nd = st[i * 2].nd + st[i * 2 + 1].nd;
} else if (st[i * 2].st < st[i * 2 + 1].st) {
st[i].st = st[i * 2].st;
st[i].nd = st[i * 2].nd;
} else {
st[i].st = st[i * 2 + 1].st;
st[i].nd = st[i * 2 + 1].nd;
}
}
void rob(int i, int j) {
vector<int> v = {a[i][j], a[i - 1][j], a[i][j - 1], a[i - 1][j - 1]};
sort(v.begin(), v.end());
aktualizuj(0, h * w - 1, v[0], v[1] - 1, 1, 1);
aktualizuj(0, h * w - 1, v[2], v[3] - 1, 5, 1);
}
void rob2(int i, int j) {
rob(i, j);
rob(i + 1, j);
rob(i, j + 1);
rob(i + 1, j + 1);
}
void mrob(int i, int j) {
vector<int> v = {a[i][j], a[i - 1][j], a[i][j - 1], a[i - 1][j - 1]};
sort(v.begin(), v.end());
aktualizuj(0, h * w - 1, v[0], v[1] - 1, -1, 1);
aktualizuj(0, h * w - 1, v[2], v[3] - 1, -5, 1);
}
void mrob2(int i, int j) {
mrob(i, j);
mrob(i + 1, j);
mrob(i, j + 1);
mrob(i + 1, j + 1);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
h = H;
w = W;
for (int i = 0; i <= h + 1; i ++) {
for (int j = 0; j <= w + 1; j ++) {
a[i].pb(h * w);
}
}
for (int i = 0; i < h * w; i ++) {
pos[i].st = R[i];
pos[i].nd = C[i];
pos[i].st ++;
pos[i].nd ++;
a[pos[i].st][pos[i].nd] = i;
}
buduj(0, h * w - 1, 1);
for (int i = 1; i <= h + 1; i ++) {
for (int j = 1; j <= w + 1; j ++) {
rob(i, j);
}
}
}
int swap_seats(int x, int y) {
mrob2(pos[x].st, pos[x].nd);
mrob2(pos[y].st, pos[y].nd);
swap(pos[x], pos[y]);
swap(a[pos[x].st][pos[x].nd], a[pos[y].st][pos[y].nd]);
rob2(pos[x].st, pos[x].nd);
rob2(pos[y].st, pos[y].nd);
return st[1].nd;
}
