//fast
#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(n) for(int i = 0 ; i<n ; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
int n,m;
vector<vector<int>> chart;
vector<int> wier;
vector<int> kol;
const int base = (1<<20);
int ile[base*2];
int sum[base*2][2];
int mini[base*2][2];
void print(){
cout << " " << ile[1] << '\n';
cout << " " << ile[2] << ' ' << ile[3] << " \n";
cout << ile[4] << ' ' << ile[5] << ' ' << ile[6] << ' ' << ile[7] << '\n';
cout << " " << mini[1][0] << '\n';
cout << " " << mini[2][0] << ' ' << mini[3][0] << " \n";
cout << mini[4][0] << ' ' << mini[5][0] << ' ' << mini[6][0] << ' ' << mini[7][0] << '\n';
cout << " " << mini[1][1] << '\n';
cout << " " << mini[2][1] << ' ' << mini[3][1] << " \n";
cout << mini[4][1] << ' ' << mini[5][1] << ' ' << mini[6][1] << ' ' << mini[7][1] << '\n';
cout << " " << sum[1][0] << '\n';
cout << " " << sum[2][0] << ' ' << sum[3][0] << " \n";
cout << sum[4][0] << ' ' << sum[5][0] << ' ' << sum[6][0] << ' ' << sum[7][0] << '\n';
cout << " " << sum[1][1] << '\n';
cout << " " << sum[2][1] << ' ' << sum[3][1] << " \n";
cout << sum[4][1] << ' ' << sum[5][1] << ' ' << sum[6][1] << ' ' << sum[7][1] << '\n';
}
void dodaj(int l, int r, int p, int k, int w, int c, bool xd){
if (r<p || k<l) return;
if (p<=l && r<=k){
mini[w][xd]+=c;
sum[w][xd]+=c;
return;
}
dodaj(l,(l+r)/2,p,k,w*2,c,xd);
dodaj((l+r)/2+1,r,p,k,w*2+1,c,xd);
if (mini[w*2][0]<mini[w*2+1][0]){
mini[w][0] = mini[w*2][0];
mini[w][1] = mini[w*2][1];
ile[w] = ile[w*2];
}else if (mini[w*2][0]>mini[w*2+1][0]){
mini[w][0] = mini[w*2+1][0];
mini[w][1] = mini[w*2+1][1];
ile[w] = ile[w*2+1];
}else{
if (mini[w*2][1]<mini[w*2+1][1]){
mini[w][0] = mini[w*2][0];
mini[w][1] = mini[w*2][1];
ile[w] = ile[w*2];
}else if (mini[w*2][1]>mini[w*2+1][1]){
mini[w][0] = mini[w*2+1][0];
mini[w][1] = mini[w*2+1][1];
ile[w] = ile[w*2+1];
}else{
mini[w][0] = mini[w*2][0];
mini[w][1] = mini[w*2][1];
ile[w] = ile[w*2+1]+ile[w*2];
}
}
mini[w][0]+=sum[w][0];
mini[w][1]+=sum[w][1];
}
void smallsort(vector<int> &v){
if (v[1]<v[0]) swap(v[0],v[1]);
if (v[3]<v[2]) swap(v[2],v[3]);
if (v[2]<v[0]) swap(v[0],v[2]);
if (v[2]<v[1]) swap(v[1],v[2]);
if (v[3]<v[1]) swap(v[1],v[3]);
if (v[3]<v[2]) swap(v[2],v[3]);
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
for (int i = base ; i<base*2 ; i++) ile[i] = 1;
for (int i = 19 ; i>=0 ; i--){
for (int j = (1<<i) ; j<(1<<(i+1)) ; j++){
ile[j] = ile[j*2]+ile[j*2+1];
}
}
n = h;
m = w;
wier = r;
kol = c;
chart.resize(n+2);
rep(h+2){
chart[i].resize(m+2);
}
for (int i = 0 ; i<n*m ; i++){
chart[r[i]+1][c[i]+1] = i;
wier[i]++;
kol[i]++;
}
for (int i = 0 ; i<m+2 ; i++){
chart[0][i] = base;
chart[n+1][i] = base;
}
for (int i = 0 ; i<n+2 ; i++){
chart[i][0] = base;
chart[i][m+1] = base;
}
for (int i = 0 ; i<=n ; i++){
for (int j = 0 ; j<=m ; j++){
vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
smallsort(v);
dodaj(0,base-1,v[0],v[1]-1,1,1,0);
if (v[2]>(n*m)) continue;
dodaj(0,base-1,v[2],v[3]-1,1,1,1);
}
}
}
int swap_seats(int a, int b){
for (int i = wier[a]-1 ; i<=wier[a] ; i++){
for (int j = kol[a]-1 ; j<=kol[a] ; j++){
vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
smallsort(v);
dodaj(0,base-1,v[0],v[1]-1,1,-1,0);
if (v[2]>(n*m)) continue;
dodaj(0,base-1,v[2],v[3]-1,1,-1,1);
}
}
for (int i = wier[b]-1 ; i<=wier[b] ; i++){
for (int j = kol[b]-1 ; j<=kol[b] ; j++){
vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
smallsort(v);
dodaj(0,base-1,v[0],v[1]-1,1,-1,0);
if (v[2]>(n*m)) continue;
dodaj(0,base-1,v[2],v[3]-1,1,-1,1);
}
}
swap(chart[wier[a]][kol[a]],chart[wier[b]][kol[b]]);
swap(wier[a],wier[b]);
swap(kol[a],kol[b]);
for (int i = wier[a]-1 ; i<=wier[a] ; i++){
for (int j = kol[a]-1 ; j<=kol[a] ; j++){
vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
smallsort(v);
dodaj(0,base-1,v[0],v[1]-1,1,1,0);
if (v[2]>(n*m)) continue;
dodaj(0,base-1,v[2],v[3]-1,1,1,1);
}
}
for (int i = wier[b]-1 ; i<=wier[b] ; i++){
for (int j = kol[b]-1 ; j<=kol[b] ; j++){
vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
smallsort(v);
dodaj(0,base-1,v[0],v[1]-1,1,1,0);
if (v[2]>(n*m)) continue;
dodaj(0,base-1,v[2],v[3]-1,1,1,1);
}
}
return (n*m)-base+ile[1];
}
/*int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int h,w,q;
cin >> h >> w >> q;
vector<int> r(h*w);
vector<int> c(h*w);
rep(h*w){
cin >> r[i] >> c[i];
}
give_initial_chart(h,w,r,c);
rep(q){
int a,b;
cin >> a >> b;
cout << swap_seats(a,b) << '\n';
}
}*/
