很久以来，拜特尼亚（Bajtocja）的统治者们都有举办盛大舞会的传统，拜图尔（Bajtur）国王也不例外。然而，每当他举办舞会时，总觉得缺少点什么。因此，他决定在下一次舞会中加入艺术杂技表演，以此来增色。

为此，他委托首席顾问准备表演编排，顾问很快就提出了他的构想。

根据顾问的计划，表演将由 $n^2$ 名杂技演员参与，其中 $n$ 是某个自然数。在表演的最后，他们将排成 $n$ 行，每行恰好站有 $n$ 名杂技演员，从而形成一个 $n \times n$ 的方阵。在表演开始时，每位艺术家要么带着燃烧的呼啦圈跳舞，要么不带。午夜钟声敲响的那一刻，一些原本带着呼啦圈的杂技演员可以将呼啦圈扔给那些之前没带呼啦圈的演员。每位艺术家最多只能从另一人那里接收一个呼啦圈。

所有人将在同一时刻进行投掷。他们都是专业人士，因此呼啦圈在空中绝对不会相撞，但这里有一个窍门：每次投掷必须在同一行或同一列的艺术家之间进行。

值得一提的是，拜图尔国王喜欢大场面，因此杂技演员的数量可能非常庞大。顾问在制定计划时，首先确定了 $n$，并假设所有杂技演员在表演开始时都没有燃烧的呼啦圈。随后，他进行了 $m$ 次操作，每次选择一个行区间和一个列区间，确定一个矩形区域，并指出该矩形内的所有杂技演员都应改变他们开始表演时的状态（即：如果之前计划带呼啦圈，则改为不带，反之亦然）。

拜图尔在看过顾问的构想后，立刻明白为了让表演尽可能壮观，呼啦圈投掷的总数应该尽可能多。他想知道这个数字，但这并不简单，因为他不断地对计划进行修改。他总共进行了 $q$ 次修改，每次修改涉及选择一名特定的杂技演员并改变他开始表演时的状态（即：如果他原本计划带呼啦圈，则改为不带，反之亦然）。国王的修改会永久保留在计划中，即如果某次修改涉及某位杂技演员，该修改将一直有效，除非国王再次选择他。

因此，顾问的任务并不简单。请帮助他，对于区间 $[0, q]$ 中的每一个 $i$，计算在考虑了国王的前 $i$ 次修改后，可能发生的最大投掷次数。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n \le 300\,000, 0 \le m, q \le 300\,000$)。

接下来的 $m$ 行包含顾问用于创建计划的矩形描述。每行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$ ($1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le n$)，表示该变更影响了所有位于第 $x_1$ 行到第 $x_2$ 行（含）以及第 $y_1$ 列到第 $y_2$ 列（含）的杂技演员。行和列均从 $1$ 到 $n$ 编号。

接下来的 $q$ 行包含国王的修改描述；第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n$)，表示第 $i$ 次修改影响了位于第 $a_i$ 行第 $b_i$ 列的杂技演员。

输出格式

输出应包含 $q+1$ 行，每行包含一个整数。第 $i$ 行的数字应表示在考虑了 $i-1$ 次国王修改后的最大可能投掷次数。

样例

样例输入 1

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

样例输出 1

6
7
7
8
7

样例输入 2

7 2 0
1 1 6 6
2 2 7 7

样例输出 2

22

说明 1

下图展示了第一次国王修改后的情况。开始时带有呼啦圈的杂技演员用粗圆圈标出。箭头显示了可能的投掷路径：

子任务

• 在某些测试组中，$n \le 50, m \le 10\,000$ 且 $q = 0$。
• 在其他测试组中，$n \le 200, m \le 100\,000$ 且 $q \le 10$。
• 在其他测试组中，$n \le 2000, m \le 100\,000$ 且 $q \le 5000$。
• 在另一些测试组中，$q = 0$。

对于上述每种情况，至少存在一个对应的测试组。

此外，每个测试组至少满足以下条件之一： 组内每个测试的 $n \le 2000$。 该组测试的时间限制为 12 秒。

所有测试的时间限制统一为 5 秒。