#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
int R, C;
vector< vector<int> > table;
vector<int> pos_R, pos_C;
vector< set<int> > row_lst;
vector<int> rowmin_top, rowmin_bot;
vector<int> sdiv;
vector< vector<int> > group_min, group_max;
vector<int> group1000_min, group1000_max;
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
if(H > W) {
swap(H, W);
swap(r, c);
}
R = H;
C = W;
pos_R = r, pos_C = c;
table.resize(R, vector<int>(C));
for(int i = 0; i < H*W; i++) table[r[i]][c[i]] = i;
row_lst.resize(R);
for(int i = 0; i < H*W; i++) row_lst[r[i]].insert(i);
rowmin_top.resize(R+1, R*C);
rowmin_bot.resize(R+1, R*C);
sdiv.resize(R, 0);
for(int i = 0; i < R; i++)
for(int j = 2; j*j <= i+1; j++) if((i+1)%j == 0) sdiv[i] = j-1;
group_min.resize(R);
group_max.resize(R);
for(int i = 0; i < R; i++) {
group_min[i].resize(R*C/(i+1), C);
group_max[i].resize(R*C/(i+1), 0);
for(int j = 0; j < R*C/(i+1); j++) {
if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
}
else if(i < 15) for(int k = 0; k < i+1; k++) {
group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
}
else {
int cur = j*(i+1);
while(cur%13 != 0) {
group_min[i][j] = min(group_min[i][j], pos_C[cur]);
group_max[i][j] = max(group_max[i][j], pos_C[cur]);
cur++;
}
while(cur+13 <= (j+1)*(i+1)) {
group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
cur += 13;
}
while(cur < (j+1)*(i+1)) {
group_min[i][j] = min(group_min[i][j], pos_C[cur]);
group_max[i][j] = max(group_max[i][j], pos_C[cur]);
cur++;
}
}
}
}
group1000_min.resize(R*C/1000, C);
group1000_max.resize(R*C/1000, 0);
for(int i = 0; i < R*C/1000; i++) for(int j = 0; j < 1000; j++) {
group1000_min[i] = min(group1000_min[i], pos_C[i*1000+j]);
group1000_max[i] = max(group1000_max[i], pos_C[i*1000+j]);
}
}
int swap_seats(int a, int b) {
// if(C > 10000) return 0;
row_lst[pos_R[a]].erase(a);
row_lst[pos_R[b]].erase(b);
swap(table[pos_R[a]][pos_C[a]], table[pos_R[b]][pos_C[b]]);
swap(pos_R[a], pos_R[b]);
swap(pos_C[a], pos_C[b]);
row_lst[pos_R[a]].insert(a);
row_lst[pos_R[b]].insert(b);
for(int i = 0; i < R; i++) if(a/(i+1) < R*C/(i+1)) {
group_min[i][a/(i+1)] = C;
group_max[i][a/(i+1)] = 0;
int j = a/(i+1);
if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
}
else if(i < 15) for(int k = 0; k < i+1; k++) {
group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
}
else {
int cur = j*(i+1);
while(cur%13 != 0) {
group_min[i][j] = min(group_min[i][j], pos_C[cur]);
group_max[i][j] = max(group_max[i][j], pos_C[cur]);
cur++;
}
while(cur+13 <= (j+1)*(i+1)) {
group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
cur += 13;
}
while(cur < (j+1)*(i+1)) {
group_min[i][j] = min(group_min[i][j], pos_C[cur]);
group_max[i][j] = max(group_max[i][j], pos_C[cur]);
cur++;
}
}
}
for(int i = 0; i < R; i++) if(b/(i+1) < R*C/(i+1)) {
group_min[i][b/(i+1)] = C;
group_max[i][b/(i+1)] = 0;
int j = b/(i+1);
if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
}
else if(i < 15) for(int k = 0; k < i+1; k++) {
group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
}
else {
int cur = j*(i+1);
while(cur%13 != 0) {
group_min[i][j] = min(group_min[i][j], pos_C[cur]);
group_max[i][j] = max(group_max[i][j], pos_C[cur]);
cur++;
}
while(cur+13 <= (j+1)*(i+1)) {
group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
cur += 13;
}
while(cur < (j+1)*(i+1)) {
group_min[i][j] = min(group_min[i][j], pos_C[cur]);
group_max[i][j] = max(group_max[i][j], pos_C[cur]);
cur++;
}
}
}
if(a/1000 < R*C/1000) {
group1000_min[a/1000] = C;
group1000_max[a/1000] = 0;
for(int j = 0; j < 1000; j++) {
group1000_min[a/1000] = min(group1000_min[a/1000], pos_C[(a/1000)*1000+j]);
group1000_max[a/1000] = max(group1000_max[a/1000], pos_C[(a/1000)*1000+j]);
}
}
if(b/1000 < R*C/1000) {
group1000_min[b/1000] = C;
group1000_max[b/1000] = 0;
for(int j = 0; j < 1000; j++) {
group1000_min[b/1000] = min(group1000_min[b/1000], pos_C[(b/1000)*1000+j]);
group1000_max[b/1000] = max(group1000_max[b/1000], pos_C[(b/1000)*1000+j]);
}
}
int ans = 0, cur_max = 0;
int rl = pos_R[0], rr = pos_R[0], cl = pos_C[0], cr = pos_C[0];
for(int i = 0; i < pos_R[0]; i++) rowmin_top[i+1] = min(rowmin_top[i], *begin(row_lst[i]));
for(int i = R-1; i >= pos_R[0]; i--) rowmin_bot[i] = min(rowmin_bot[i+1], *begin(row_lst[i]));
for(int i = 0; i < R; i++) {
int cur_out_min = min(rowmin_bot[rr+1], rowmin_top[rl]);
int D = cur_max / (rr-rl+1);
cl = min(cl, group_min[rr-rl][D]);
cr = max(cr, group_max[rr-rl][D]);
cur_max = (D+1) * (rr-rl+1) - 1;
while((rr-rl+1)*(cr-cl+1) <= cur_out_min) {
if((rr-rl+1)*(cr-cl+1) == cur_max+1) ans++;
D++;
if(cur_max+rr-rl+1 >= cur_out_min) break;
cur_max += rr-rl+1;
if(D < R*C/(rr-rl+1)) {
cl = min(cl, group_min[rr-rl][D]);
cr = max(cr, group_max[rr-rl][D]);
}
}
if(i == R-1) break;
int min_top = (rl == 0) ? R*C : *begin(row_lst[rl-1]);
int min_bot = (rr == R-1) ? R*C : *begin(row_lst[rr+1]);
if(min_top < min_bot) rl--;
else rr++;
}
return ans;
}
