Background

This is an interactive problem, but here you should submit a full program.

Problem Description

You are going to hold an international programming contest in a rectangular hall. The hall has $HW$ seats ($H$ rows and $W$ columns). Rows are numbered from $0$ to $H - 1$, and columns are numbered from $0$ to $W - 1$. The seat in row $r$ and column $c$ is denoted by $(r, c)$. There are $HW$ contestants, numbered from $0$ to $HW - 1$. You have prepared a seating plan: contestant $i(0 \leq i \leq HW - 1)$ is assigned to seat $(R_i, C_i)$. The seating plan is a one-to-one correspondence between contestants and seats.

A set of seats $S$ in the hall is called rectangular if there exist integers $r_1, r_2, c_1$, and $c_2$ such that:

• $0 \leq r_1 \leq r_2 \leq H - 1$.
• $0 \leq c_1 \leq c_2 \leq W - 1$.
• $S$ is exactly the set of all seats $(r, c)$ that satisfy $r_1 \leq r \leq r_2$ and $c_1 \leq c \leq c_2$.

If a rectangular set of seats contains $k(1 \leq k \leq HW)$ seats, and the contestant IDs assigned to these seats are exactly from $0$ to $k - 1$, then this set is nice. The niceness of a seating plan is defined as the number of nice rectangular seat sets in the plan.

After you finish the seating plan, you will receive some requests to swap the seats of two contestants. Specifically, there are $Q$ such requests, numbered from $0$ to $Q - 1$ in time order. Request $j(0 \leq j \leq Q - 1)$ wants to swap the seats of contestants $A_j$ and $B_j$. You accept each request immediately and update the seating plan. After each update, your task is to compute the niceness of the current seating plan.

Input Format

The first line contains three positive integers $H, W, Q$, as described above.

The next $HW$ lines each contain two non-negative integers. In these $HW$ lines, line $i$ contains $R_{i - 1}, C_{i - 1}$, i.e., the row and column of the initial seat of contestant $i - 1$.

The next $Q$ lines each contain two non-negative integers. In these $Q$ lines, line $j$ contains $A_{j - 1}, B_{j - 1}$, i.e., the IDs of the two contestants whose seats should be swapped in request $j - 1$.

Output Format

Output $Q$ lines. Each line contains one integer. The integer on line $i$ is the niceness of the current seating plan after processing swap request $i - 1$ in time order.

2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5

3
4

1 5 3
0 0
0 1
0 2
0 3
0 4
0 1
0 3
4 0

5
3
2

Hint

Constraints

• $1 \leq H$.
• $1 \leq W$.
• $HW \leq 1, 000, 000$.
• $0 \leq R_i \leq H - 1(0 \leq i \leq HW - 1)$.
• $0 \leq C_i \leq W - 1(0 \leq i \leq HW - 1)$.
• $(R_i, C_i) \neq (R_j, C_j)(0 \leq i < j \leq HW - 1)$.
• $1 \leq Q \leq 50, 000$.
• $0 \leq A_j \leq HW - 1(0 \leq j \leq Q - 1)$.
• $0 \leq B_j \leq HW - 1(0 \leq j \leq Q - 1)$.
• $A_j \neq B_j(0 \leq j \leq Q - 1)$.

Subtasks

• 1. (5 points) $HW \leq 100$, $Q \leq 5, 000$.
• 2. (6 points) $HW \leq 10, 000$, $Q \leq 5, 000$.
• 3. (20 points) $H \leq 1, 000$, $W \leq 1, 000$, $Q \leq 5, 000$.
• 4. (6 points) $Q \leq 5, 000$, $|A_j - B_j| \leq 10, 000(0 \leq j \leq Q - 1)$.
• 5. (33 points) $H = 1$.
• 6. (30 points) No additional constraints.

Translated by ChatGPT 5