Bảng

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 (bắt đầu từ $0$), ô 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ỗi ô một số.

Một bảng con là một bảng hình chữ nhật gồm các ô liên tiếp của bảng ban đầu, 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\times b$ được gọi là đẹp nếu trong đó có đủ các số từ $0$ đến $a·b-1$. Bản thân toàn bộ bảng cũng là một bảng con, và hiển nhiên nó luôn là bảng đẹp.

Có $Q$ truy vấn, mỗi truy vấn đổi chỗ hai số $X$ và $Y$ trong bảng. Các truy vấn được thực hiện lần lượt: truy vấn sau áp dụng trên bảng đã bị thay đổi bởi các truy vấn trước. Sau mỗi truy vấn, hãy đếm số bảng con đẹp của bảng hiện tại.

Dữ liệu vào

• Dòng đầu tiên ghi ba số nguyên $N,M,Q$ ($1\le N·M\le {10}^6$, $1\le Q\le 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: dòng thứ $i+1$ trong số này ($0\le i<N·M$) ghi hai số nguyên $r_i,c_i$ ($0\le r_i<N$, $0\le c_i<M$) cho biết số $i$ nằm ở hàng $r_i$, cột $c_i$. Các ô $(r_i,c_i)$ đôi một khác nhau.
• $Q$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $X,Y$ ($0\le X,Y<N·M$) là truy vấn đổi vị trí hai số $X$ và $Y$. Nếu $X=Y$ thì bảng không thay đổi.

Dữ liệu ra

In ra $Q$ dòng, dòng thứ $j$ là số bảng con đẹp sau truy vấn thứ $j$.

Ràng buộc

• $1\le N·M\le {10}^6$.
• $1\le Q\le 5·{10}^4$.

Subtasks

• Subtask 1 ($15\%$ số điểm): $N·M\le 100$, $Q\le 5000$.
• Subtask 2 ($25\%$ số điểm): $N·M·Q\le 5·{10}^7$.
• Subtask 3 ($20\%$ số điểm): $N,M\le {10}^4$, $Q\le 5000$.
• Subtask 4 ($10\%$ số điểm): $Q\le 5000$, chênh lệch giữa hai số đổi chỗ nhỏ hơn ${10}^4$ ($|X-Y|<{10}^4$).
• Subtask 5 ($10\%$ số điểm): $N=1$.
• Subtask 6 ($20\%$ số điểm): Không có giới hạn nào thêm.

Ví dụ