#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0; char ch; bool f=0;
    while(((ch=getchar())<'0'||ch>'9')&&ch!='-') ;
    if(ch=='-') f=1;
    else x=ch^48;
    while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48);
    return f?-x:x;
}
const int N=3e6+55;
const int dx[4]={-1,-1,0,0};
const int dy[4]={-1,0,-1,0};
int n,m,q;
struct POS{
	int x,y;
	bool operator<(const POS &t)const{
		if(x^t.x) return x<t.x;
		return y<t.y;
	}
}s[N];
int a[N];
int id(int x,int y){
	return x*(m+2)+y+1;
}
struct tr{
	struct tree{
		long long mn,cnt,bz;
	}t[N<<2];
	#define ls (p<<1)
	#define rs (p<<1|1)
	void up(int p){
		t[p].mn=min(t[ls].mn,t[rs].mn);
		t[p].cnt=(t[p].mn==t[ls].mn)*t[ls].cnt+(t[p].mn==t[rs].mn)*t[rs].cnt;
	}
	void cg(int p,long long v){
		t[p].bz+=v,t[p].mn+=v;
	}
	void down(int p){
		if(t[p].bz){
			cg(ls,t[p].bz),cg(rs,t[p].bz),t[p].bz=0;
		}
	}
	void build(int p,int l,int r){
		t[p].mn=0,t[p].cnt=r-l+1;
		if(l==r) return;
		int mid=(l+r)/2;
		build(ls,l,mid),build(rs,mid+1,r);
	}
	void ad(int p,int st,int en,int l,int r,long long v){
		if(st>en||r<st||en<l) return;
		if(st<=l&&r<=en){
			cg(p,v); return;
		}
		int mid=(l+r)/2;
		down(p);
		if(st<=mid) ad(ls,st,en,l,mid,v);
		if(mid<en) ad(rs,st,en,mid+1,r,v);
		up(p);
	}
	int ask(){
		return (t[1].mn==4)*t[1].cnt;
	}
	#undef ls
	#undef rs
}T;
int p[6];
void ins(int x,int y,int v){
	for(int i=0;i<4;i++) p[i]=a[id(x+dx[i],y+dy[i])];
	sort(p,p+4);
	T.ad(1,p[0],p[1]-1,1,n*m,v);
	T.ad(1,p[2],p[3]-1,1,n*m,v);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
	n=H,m=W;
	for(int i=1;i<=n*m;i++){
		int x=R[i-1],y=C[i-1]; x++,y++;
		s[i]={x,y};
		a[id(x,y)]=i;
	}
	T.build(1,1,n*m);
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
			if(!i||!j||i==n+1||j==m+1) a[id(i,j)]=n*m+1;
		}
	}
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=m+1;j++){
			ins(i,j,1);
		}
	}
}
int swap_seats(int t1,int t2){
	t1++,t2++;
	vector<POS> tp,p; p.clear(),tp.clear();
	tp.push_back({s[t1].x,s[t1].y});
	tp.push_back({s[t1].x,s[t1].y+1});
	tp.push_back({s[t1].x+1,s[t1].y});
	tp.push_back({s[t1].x+1,s[t1].y+1});
	tp.push_back({s[t2].x,s[t2].y});
	tp.push_back({s[t2].x,s[t2].y+1});
	tp.push_back({s[t2].x+1,s[t2].y});
	tp.push_back({s[t2].x+1,s[t2].y+1});
	sort(tp.begin(),tp.end());
	for(auto [x,y]:tp){
		if(!p.size()||p.back().x!=x||p.back().y!=y) p.push_back({x,y});
	}
	for(auto [x,y]:p){
		ins(x,y,-1);
	}
	swap(a[id(s[t1].x,s[t1].y)],a[id(s[t2].x,s[t2].y)]);
	swap(s[t1],s[t2]); 
//		for(int i=1;i<=n*m;i++)cout<<s[i].x<<" "<<s[i].y<<"!!\n";
	for(auto [x,y]:p){
		ins(x,y,1);
	}
//		cout<<T.t[1].mn<<" "<<T.t[1].cnt<<"??\n";
//		cout<<T.ask()<<"!\n";
	return T.ask();
}