Cho một hình chữ nhật gồm \(N\) hàng, \(M\) cột, các hàng được đánh số từ trên xuống dưới, các cột đánh số từ trái qua phải, ô trái trên là ô \((0;0),\) ô phải dưới là ô \((N - 1,\ M - 1)\). Người ta viết các số từ \(0\ \)đến \(N*M - 1\) vào bảng trên một cách ngẫu nhiên.

Một bảng con là bảng hình chữ nhật có kích thước nhỏ hơn hoặc bằng bảng ban đầu. Một bảng con kích thước\(\ a*b\) được gọi là đẹp nếu trong đó có đủ các số từ 0 đến \(a*b - 1.\)

Có \(Q\) truy vấn, hãy đếm số bảng con đẹp trong bảng ban đầu sau khi đổi chỗ hai số \(X\) với số \(Y\), biết bảng ban đầu đương nhiên là bảng đẹp.

Dữ liệu vào:

+ Dòng đầu tiên ghi ba số \(N,\ M,\ Q\ (1 \leq N*M \leq 10^{6};Q \leq {5.10}^{4})\ \)là số hàng, số cột và số truy vấn.

+ \(N*M\) dòng tiếp theo mô tả tọa độ các số trong bảng thuộc dòng và cột nào\(.\)

+ \(Q\ \)dòng tiếp theo ghi các số \(X,\ Y\) là truy vấn đổi vị trí hai số \(X,\ Y\).

Kết quả:

+ Ghi ra \(Q\) số là câu trả lời cho \(Q\) câu hỏi là đếm số bảng con đẹp.

Ví dụ:

Input	Output	Giải thích
2 3 2 0 0 1 0 1 1 0 1 0 2 1 2 0 5 0 5	3 4		Bảng ban đầu có 4 bảng con đẹp như hình, sau khi đổi chỗ số 0 và số 5 thì số bảng đẹp còn là 3

Ràng buộc:

+ Subtask 1: 15% điểm có \(N*M \leq 100,\ Q \leq 5000;\)

+ Subtask 2: 25% điểm có \(M*N*Q \leq {5.10}^{7};\)

+ Subtask 3: 20% điểm có \(N,\ M \leq 10000,\ Q \leq 5000;\)

+ Subtask 4: 10% điểm có \(Q \leq 5000,\ \)chênh lệch giữa hai số đổi chỗ \(X,\ Y\ \)nhỏ hơn \(10^{4};\)

+ Subtask 5: 10% điểm có \(N = 1\);

+ Subtask 6: 20% điểm không có giới hạn nào thêm.