Problem Description

You are organizing an international programming competition in a rectangular hall with $HW$ seats arranged in $H$ rows and $W$ columns. Rows are numbered from $0$ to $H-1$, and columns are numbered from $0$ to $W-1$. The seat at row $r$ and column $c$ is denoted as $(r, c)$. You have invited $HW$ participants, numbered from $0$ to $HW-1$. You have prepared a seating chart where the $i$-th participant (where $0 \leq i \leq HW - 1$) is assigned to seat $(R_i, C_i)$. Each participant is assigned to a unique seat.

A set of seats $S$ is considered 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 seats $(r, c)$ where $r_1 \leq r \leq r_2$ and $c_1 \leq c \leq c_2$

A rectangular set of seats containing $k$ seats ($1 \leq k \leq$) is considered beautiful if the participants assigned to these seats are exactly those numbered from $0$ to $k-1$. The beauty degree of a seating chart is defined as the number of beautiful rectangular sets of seats in the chart.

After preparing the seating chart, you will receive requests to swap the seats of two participants. Specifically, there are $Q$ such requests, numbered from $0$ to $Q-1$. The $j$-th request ($0 \leq j \leq Q - 1$) asks to swap the seats of participants $A_j$ and $B_j$. You immediately accept each request and update the seating chart. After each update, your goal is to calculate the beauty degree of the current seating chart.

Input Format

The first line of input contains three positive integers $H, W, Q$, as described in the problem statement.

The next $HW$ lines each contain two non-negative integers. The $i$-th line contains $R_{i-1}$ and $C_{i-1}$, representing the initial row and column of the participant numbered $i-1$.

The next $Q$ lines each contain two non-negative integers. The $j$-th line contains $A_{j-1}$ and $B_{j-1}$, representing the participants whose seats are to be swapped in the request numbered $j-1$.

Output Format

The output should consist of $Q$ lines, each containing a single integer. The $i$-th line should contain the beauty degree of the seating chart after processing the swap request numbered $i-1$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3
4

Sample Input #2

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

Sample Output #2

5
3
2

Notes/Hints

Constraints

• $1 \leq H$
• $1 \leq W$
• $\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) $\leq 100$, $Q \leq 5,000$
2. (6 points) $\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

见题面 Input 部分

见题面 Output 部分