#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
// #define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#define endl '\n'
#endif
// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
ll pwr(ll a,ll b){
a %= mod;
int ans = 1;
while(b){
if(b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
const int N = 1e6 + 5;
pair<int,int> tr[2 * N][2];
int tot;
int d[2 * N];
pii pos[N];
int n, h;
void build1(){
n = tot + 1;
h = sizeof(int) * 8 - __builtin_clz(n);
fr(i, n, 2 * n - 1){
tr[i][0].fi = 0, tr[i][0].se = 1;
tr[i][1].fi = 1e9, tr[i][1].se = 0;
}
for(int i = n - 1; i > 0; i--){
tr[i][0].fi = 0, tr[i][0].se = tr[i << 1][0].se + tr[i << 1 | 1][0].se;
tr[i][1].fi = 1e9, tr[i][1].se = 0;
}
}
vector<vector<int>> m;
vector<vector<bool>> active;
int dx[4] = {0, 0, -1, -1};
int dy[4] = {0, -1, 0, -1};
int pp[4] = {1, 2, 2, 1};
void apply(int p, int value){
tr[p][0].fi += value;
tr[p][1].fi += value;
if(p < n) d[p] += value;
}
void push(int p){
for(int s = h; s > 0; --s){
int i = p >> s;
if (d[i] != 0){
apply(i << 1, d[i]);
apply(i << 1 | 1, d[i]);
d[i] = 0;
}
}
}
void build(int nd) {
while(nd > 1){
nd >>= 1;
int pt1 = 0, pt2 = 0, pt = 0;
int nd1 = nd << 1, nd2 = nd1 | 1;
while(pt1 < 2 && pt2 < 2 && pt < 2){
if(tr[nd1][pt1].fi < tr[nd2][pt2].fi){
tr[nd][pt++] = tr[nd1][pt1++];
}
else if(tr[nd1][pt1].fi > tr[nd2][pt2].fi){
tr[nd][pt++] = tr[nd2][pt2++];
}
else{
tr[nd][pt++] = {tr[nd1][pt1].fi, tr[nd1][pt1].se + tr[nd2][pt2].se};
pt1++, pt2++;
}
}
tr[nd][0].fi += d[nd];
tr[nd][1].fi += d[nd];
}
}
void inc(int l, int r, int value){
r++;
l += n, r += n;
int l0 = l, r0 = r;
for(;l < r; l >>= 1, r >>= 1){
if(l & 1) apply(l++, value);
if(r & 1) apply(--r, value);
}
build(l0);
build(r0 - 1);
}
map<pii,int> queries;
void add_box(int x,int y,int val){
if(!active[x][y] && val == -1) return;
if(active[x][y] && val == 1) return;
active[x][y] = !active[x][y];
x++, y++;
vector<pii> lol;
fr(i, 0, 3){
lol.pb({m[x + dx[i]][y + dy[i]], pp[i]});
}
sort(all(lol));
if(lol[0].fi <= tot && lol[0].fi == m[x][y]){ // for 1 wala
queries[{lol[0].fi, min(lol[1].fi - 1, tot)}] += val;
}
if(lol[0].se == lol[1].se && lol[1].fi <= tot) // for 2 wale
queries[{lol[1].fi, min(lol[3].fi - 1, tot)}] += 2 * val;
else if(lol[2].fi <= tot) // for 3 wale
queries[{lol[2].fi, min(lol[3].fi - 1, tot)}] += 2 * val;
}
void give_initial_chart(int h,int w,vector<int> r,vector<int> c){
tot = h * w - 1;
build1();
m.resize(h + 2);
active.resize(h + 2);
fr(i, 0, h + 1){
m[i].resize(w + 2, 1e9);
active[i].resize(w + 2, 0);
}
fr(i, 0, tot){
pos[i] = {r[i] + 1, c[i] + 1};
m[r[i] + 1][c[i] + 1] = i;
}
for(int i = 0; i <= h; i++){
for(int j = 0; j <= w; j++){
add_box(i, j, 1);
}
}
for(auto it : queries){
if(it.se){
inc(it.fi.fi, it.fi.se, it.se);
}
}
queries.clear();
}
int swap_seats(int a,int b){
fr(i, 0, 3){
add_box(pos[a].fi + dx[i], pos[a].se + dy[i], -1);
add_box(pos[b].fi + dx[i], pos[b].se + dy[i], -1);
}
swap(pos[a], pos[b]);
m[pos[a].fi][pos[a].se] = a;
m[pos[b].fi][pos[b].se] = b;
fr(i, 0, 3){
add_box(pos[a].fi + dx[i], pos[a].se + dy[i], 1);
add_box(pos[b].fi + dx[i], pos[b].se + dy[i], 1);
}
for(auto it : queries){
if(it.se){
inc(it.fi.fi, it.fi.se, it.se);
}
}
queries.clear();
int ans = 0;
fr(i, 0, 1){
if(tr[1][i].fi == 1){
ans = tr[1][i].se;
break;
}
}
return ans;
}
