The Royal Ball

The king of Byteotia has decided to add some artistic spark to his lavish ball by introducing a peculiar performance by his circus actors. In the final act, the n² actors form an n×n square. Initially, every actor is assigned a starting state: either dancing with a flaming hoop (denoted by 1) or without one (denoted by 0). The initial configuration is determined as follows:

1. All actors start without a hoop (state 0).
2. The chief adviser then performs m rectangular operations. For each operation represented by four integers r₁, c₁, r₂, c₂ (with 1-indexed coordinates and r₁ ≤ r₂, c₁ ≤ c₂), every actor in the rectangle with top‐left corner (r₁, c₁) and bottom‐right corner (r₂, c₂) flips his state (from 0 to 1 or 1 to 0).

After the adviser’s plan is set, the king makes q modifications. In each modification, a single actor’s state is toggled (i.e. changed from 0 to 1 or from 1 to 0). These modifications are permanent – that is, once an actor’s state is changed by a modification, it remains changed for all subsequent steps unless toggled again.

At midnight during the performance, every actor who starts with a hoop is allowed to throw his hoop to another actor in the same row or in the same column, but an actor may throw at most one hoop. A hoop can only be thrown to an actor who does not have a hoop at the start. To maximize the spectacle, the king wants the number of throws to be as large as possible.

Your task is to compute, for each integer i from 0 to q (where i=0 corresponds to the configuration after the adviser's operations but before any king’s modifications, and for i ≥ 1 the configuration after the first i modifications), what is the maximum possible number of throws that can occur.

Observation: Note that an actor who starts with a hoop can throw only if in his row or his column there is at least one actor without a hoop. In other words, if an actor with a hoop is in a row that is entirely made up of ones and also in a column entirely made up of ones then he cannot throw.

This maximum number equals the total number of actors with a hoop minus the number of actors that are "isolated" in a row and column fully filled with hoops. More formally, if we let:

TotalThrows = (Total number of ones) − (Number of rows that are full of ones) × (Number of columns that are full of ones)

compute this value for each configuration.

inputFormat

The first line contains three integers n, m, q (1 ≤ n ≤ 1000 for instance, and appropriate limits for m and q). n is the dimension of the square, m is the number of rectangular flip operations, and q is the number of single-cell modifications.

Then follow m lines; each contains four integers r₁, c₁, r₂, c₂ (1-indexed, with r₁ ≤ r₂ and c₁ ≤ c₂), describing a rectangular region whose actors have their state toggled.

Then follow q lines; each contains two integers r, c (1-indexed) indicating that the state of the actor in row r, column c is to be toggled.

outputFormat

Output q+1 lines. The first line is the maximum number of throws possible after applying the m rectangular operations (before any modifications), and each subsequent line is the answer after applying the corresponding modifications cumulatively.

sample

2 1 2
1 1 2 2
1 1
2 2

0
2
2

</p>