Problem Description

This problem is translated from PA 2020 Round 5 Królewski bal.

Since ancient times, all rulers of Byteotia have held luxurious balls, and King Byteur is no exception. However, every time he organizes one, he feels that something is missing. Therefore, he decided to add some artistic elements to the next ball.

To this end, King Byteur asked his chief advisor to arrange a performance. Soon, the advisor presented his idea.

According to the advisor’s plan, $n^2$ circus performers will take part in the show, where $n$ is a positive integer. In the grand finale, they will stand in $n$ rows, with exactly $n$ performers in each row, forming an $n \times n$ square. At the start of the grand finale, each performer will dance either with a burning hula hoop or without one. At midnight, some performers who are dancing with hula hoops may throw their hula hoops to other performers who are dancing without hula hoops. Each performer is allowed to throw to at most one other performer.

All throws happen at the same time. They are professionals, so their hula hoops will definitely not collide in the air, but there is one problem: each throw must be between performers located in the same row or the same column.

It is also worth mentioning that King Byteur likes large-scale actions, so the number of performers can be extremely huge. When making the plan, the advisor first fixed the number $n$ and assumed that all performers would start the grand finale without burning hula hoops. Then, he chose $m$ specific row-and-column ranges, drew a rectangle for each, and made every performer in that area start the grand finale in the opposite way. That is, if in the previous version they started with a hula hoop, then in this version they start without one, and vice versa.

After hearing the plan, King Byteur immediately understood that, to make the show as spectacular as possible, the number of throws should be as large as possible. King Byteur wants to know this number, but this is not easy, because he keeps changing the plan. Each of his changes (he has made $q$ changes in total) involves choosing one performer and changing how they start the grand finale (i.e., if they started with a hula hoop before, now they start without one, and vice versa). The king’s changes are kept permanently in the plan, meaning that if a change applies to a performer, its effect remains until the end, unless the king changes that performer again.

Therefore, the advisor’s task is not simple. Help him: for every integer $i$ in $[0, q]$, after considering the king’s first $i$ changes, determine the maximum number of throws that can happen.

Input Format

The first line contains three integers $n, m, q$.

The next $m$ lines describe the advisor’s plan. Each line contains four integers $x_1, y_1, x_2, y_2$, meaning an operation is applied to the performers in rows $x_1$ to $x_2$ (inclusive) and columns $y_1$ to $y_2$ (inclusive). Row and column indices are from $1$ to $n$.

The next $q$ lines describe the king’s changes. The $i$-th line contains two numbers $a_i, b_i$, meaning the king toggles the state of the performer in row $a_i$ and column $b_i$.

Output Format

Output $q + 1$ lines. On the $i$-th line, output the maximum number of throws that can happen after considering the king’s first $i - 1$ changes.

4 3 4
1 2 4 2
3 1 3 4
3 2 3 2
4 4
3 2
4 3
4 4

6
7
7
8
7

7 2 0
1 1 6 6
2 2 7 7

22

Hint

Sample 1 Explanation

The figure below shows the situation after the king makes the first change. Performers who start with hula hoops are marked with bold circles, and arrows indicate possible throws.

Constraints

This problem uses bundled testdata.

• For some subtasks, $n \le 50$, $m \le 10^4$, $q = 0$.
• For some other subtasks, $n \le 200$, $m \le 10^5$, $q \le 10$.
• For some other subtasks, $n \le 2 \times 10^3$, $m \le 10^5$, $q \le 5 \times 10^3$.
• For some other subtasks, $q = 0$.

At least one subtask satisfies each of the cases above.

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 3 \times 10^5$, $0 \le m, q \le 3 \times 10^5$, $1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$, $1 \le a_i, b_i \le n$.

In addition, for each subtask, at least one of the following conditions holds:

• $n \le 2 \times 10^3$
• The time limit is $12$ seconds.

Since the specific time limits for subtasks are not given, on Luogu the time limit for all subtasks is $3$ seconds.

Translated by ChatGPT 5