#include <bits/stdc++.h>
#include "seats.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
int h,w;
vector<vector<int> > val;
vector<pair<int,int> > y;
int n;
struct ST{
struct no{
int mn=0,cnt=1,tag=0;
};
vector<no> st;
void init(int x){
st.resize(4*x);
}
void upd(int v,int k){
st[v].mn+=k;
st[v].tag+=k;
}
void pudo(int v){
upd(2*v+1,st[v].tag);
upd(2*v+2,st[v].tag);
st[v].tag=0;
}
void pull(int v){
st[v].mn=min(st[2*v+1].mn,st[2*v+2].mn);
st[v].cnt=0;
if(st[2*v+1].mn==st[v].mn){
st[v].cnt+=st[2*v+1].cnt;
}
if(st[2*v+2].mn==st[v].mn){
st[v].cnt+=st[2*v+2].cnt;
}
}
void update(int v,int L,int R,int l,int r,int k){
if(r<l){
return;
}
if(L==l && r==R){
upd(v,k);
return;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
update(2*v+1,L,m,l,r,k);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,k);
}
else{
update(2*v+1,L,m,l,m,k);
update(2*v+2,m+1,R,m+1,r,k);
}
pull(v);
}
int query(){
return st[0].cnt;
}
}st;
void ud(int a,int b,int c,int d,int k){
vector<int> g{a,b,c,d};
sort(g.begin(),g.end());
st.update(0,0,n-1,g[0],g[1]-1,k);
st.update(0,0,n-1,g[2],g[3]-1,k);
}
inline void chg(int i,int j,int t){
ud(val[i][j],val[i+1][j],val[i+1][j+1],val[i][j+1],t);
}
void give_initial_chart(int a,int b,vector<int> r,vector<int> c){
h=a;
w=b;
val.clear();
val.resize(h+2,vector<int>(w+2,h*w));
n=h*w+1;
st.init(n);
st.update(0,0,n-1,n-1,n-1,1e9);
for(int i=0;i<h*w;i++){
val[r[i]+1][c[i]+1]=i;
y.push_back({r[i]+1,c[i]+1});
}
for(int i=0;i<=h;i++){
for(int j=0;j<=w;j++){
chg(i,j,1);
}
}
}
const int dx[4]={0,0,-1,-1};
const int dy[4]={0,-1,0,-1};
int swap_seats(int a,int b){
auto c=y[a];
auto d=y[b];
for(int i=0;i<4;i++){
chg(c.fs+dx[i],c.sc+dy[i],-1);
chg(d.fs+dx[i],d.sc+dy[i],-1);
}
swap(val[c.fs][c.sc],val[d.fs][d.sc]);
for(int i=0;i<4;i++){
chg(c.fs+dx[i],c.sc+dy[i],1);
chg(d.fs+dx[i],d.sc+dy[i],1);
}
swap(y[a],y[b]);
return st.query();
}
