#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[4 * N][5];
int tot;
int lz[4 * N];
pii pos[N];
void build(int nd,int s,int e){
tr[nd][0].fi = 0, tr[nd][0].se = e - s + 1;
fr(i, 1, 4){
tr[nd][i].fi = 1e9, tr[nd][i].se = 0;
}
if(s == e) return;
int m = (s + e) >> 1;
build(nd << 1, s, m);
build(nd << 1 | 1, m + 1, e);
}
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 push_down(int nd,int s,int e){
if(!lz[nd]) return;
fr(i, 0, 4){
tr[nd][i].fi += lz[nd];
}
if(s != e){
lz[nd << 1] += lz[nd];
lz[nd << 1 | 1] += lz[nd];
}
lz[nd] = 0;
}
map<pii,int> queries;
void upd(int nd,int s,int e,int l,int r,int val){
push_down(nd, s, e);
if(s > e || s > r || e < l) return;
if(l <= s && e <= r){
lz[nd] += val;
push_down(nd, s, e);
return;
}
int m = (s + e) >> 1;
upd(nd << 1, s, m, l, r, val);
upd(nd << 1 | 1, m + 1, e, l, r, val);
int pt1 = 0, pt2 = 0;
int pt = 0;
int nd1 = nd << 1, nd2 = nd1 | 1;
while(pt1 < 5 && pt2 < 5 && pt < 5){
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++;
}
}
while(pt1 < 5 && pt < 5){
tr[nd][pt++] = tr[nd1][pt1++];
}
while(pt2 < 5 && pt < 5){
tr[nd][pt++] = tr[nd2][pt2++];
}
}
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].se <= tot)
queries[{lol[1].fi, min(lol[2].fi - 1, tot)}] += 5 * val;
if(lol[2].fi <= tot) // for 3 wale
queries[{lol[2].fi, min(lol[3].fi - 1, tot)}] += 5 * val;
}
void give_initial_chart(int h,int w,vector<int> r,vector<int> c){
tot = h * w - 1;
build(1, 0, tot);
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){
upd(1, 0, tot, 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){
upd(1, 0, tot, it.fi.fi, it.fi.se, it.se);
}
}
queries.clear();
int ans = 0;
push_down(1, 0, tot);
fr(i, 0, 4){
if(tr[1][i].fi == 1){
ans = tr[1][i].se;
break;
}
}
return ans;
}
