#include <bits/stdc++.h>
#ifndef SKY
#include "seats.h"
#endif // SKY
using namespace std;
#define N 1000010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
int n,m,ans;
ii pos[N];
int vet()
{
int top=pos[0].fs,bot=pos[0].fs,lef=pos[0].sc,righ=pos[0].sc,res=1;
for(int i=1;i<n*m;i++)
{
top=min(top,pos[i].fs);
bot=max(bot,pos[i].fs);
lef=min(lef,pos[i].sc);
righ=max(righ,pos[i].sc);
if((bot-top+1)*(righ-lef+1)==i+1)
res++;
}
return res;
}
struct haha
{
int lef,righ,top,bot;
};
haha get_max(haha A,haha B)
{
return{min(A.lef,B.lef),max(A.righ,B.righ),min(A.top,B.top),max(A.bot,B.bot)};
};
struct IT
{
haha ST[N*4];
void update(int id,int l,int r,int i,ii val)
{
if(l>i||r<i)
return;
if(l==r)
{
ST[id]={val.sc,val.sc,val.fs,val.fs};
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,i,val);
update(id*2+1,mid+1,r,i,val);
ST[id]=get_max(ST[id*2],ST[id*2+1]);
}
haha get(int id,int l,int r,int u,int v)
{
if(l>v||r<u)
return{100000000,-100000000,100000000,-100000000};
if(l>=u&&r<=v)
return ST[id];
int mid=(l+r)/2;
return get_max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
}T;
int solve(int l,int r)
{
haha val=T.get(1,1,n*m,1,l+1);
int res=0,vt=l;
while(vt<=r)
{
if(vt+1==(val.righ-val.lef+1)*(val.bot-val.top+1))
res++;
int them=max(1,(val.righ-val.lef+1)*(val.bot-val.top+1)-(vt+1));
val=T.get(1,1,n*m,1,vt+them+1);
vt+=them;
}
return res;
}
int swap_seats(int a, int b)
{
if(a>b)
swap(a,b);
ans-=solve(a,b-1);
swap(pos[a],pos[b]);
T.update(1,1,n*m,a+1,pos[a]);
T.update(1,1,n*m,b+1,pos[b]);
ans+=solve(a,b-1);
return ans;
}
void give_initial_chart(int NNN, int MMM, std::vector<int> R, std::vector<int> C)
{
n=NNN;
m=MMM;
for(int i=0;i<n*m;i++)
pos[i]={R[i],C[i]};
ans=vet();
for(int i=0;i<n*m;i++)
T.update(1,1,n*m,i+1,pos[i]);
//cout<<ans<<endl;
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
vector<int>R(n*m),C(n*m);
for(int i=0;i<n*m;i++)
cin>>R[i]>>C[i];
give_initial_chart(n,m,R,C);
int q;
cin>>q;
while(q--)
{
int a,b;
cin>>a>>b;
cout<<swap_seats(a,b)<<endl;
}
return 0;
}
#endif
