「POI 2020/2021 R1」Tablica binarna

题目描述

矩阵 $A$ 有 $n$ 行 $m$ 列，行自上到下编号为 $1$ 至 $n$，列自左到右编号为 $1$ 到 $m$，因此可以用 $(i,j)$ 表示矩阵的第 $i$ 行第 $j$ 列的元素。且矩阵 $A$ 中每个元素的值为 $0$ 或 $1$。

最初，矩阵内的所有元素的值均为 $0$。接下来可以对该矩阵执行 $q$ 次修改操作。每次操作将给出四个参数 $i_1,j_1,i_2,j_2$，表示将以 $(i_1,j_1)$ 为左上角，$(i_2,j_2)$ 为右下角的矩形内的所有元素的值翻转（从 $0$ 变成 $1$，或从 $1$ 变为 $0$）。

如果一次操作中，矩形的左上角与矩阵的左上角重合（即 $i_1=j_1=1$），则称这次修改操作是简单的。

现在你想要知道，在每次对矩阵执行修改操作后，需要执行至少多少次简单的修改操作，使得矩阵内所有元素的值全部变为 $0$。

输入格式

输入第一行三个整数 $n, m, q$，分别代表矩阵的行数，列数，操作的次数。

接下来 $q$ 行，每行四个整数 $i_1, j_1, i_2, j_2$，描述一次修改操作。保证 $1 \leq i_1 \leq i_2 \leq n$，$1 \leq j_1 \leq j_2 \leq m$。

输出格式

输出 $q$ 行。第 $i$ 行输出一个整数，表示在第 $i$ 次修改过后，需要执行至少多少次简单的修改操作，使得矩阵内所有元素的值全部变为 $0$。

样例 1

输入

2 3 3
1 2 2 2
1 1 2 1
1 2 1 3

输出

2
1
3

样例 2

输入

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

输出

1
1
1
1
3
3
3
1
3
3
3
1
3
3
3
1

该样例满足 $n=m=4$，$q=16$，且每次修改操作按照自上而下，从左到右的顺序修改矩阵中的某一个元素。

样例 3

见附加文件下 tab2.in 和 tab2.out。

该样例满足 $n=1$，$m=q=10^3$，第 $i$ 次修改操作的四个参数分别是 $1, m+1−i, 1, m$。

样例 4

见附加文件下 tab3.in 和 tab3.out。

该样例满足 $n=m=10^3$，$q=10^5$，第 $i$ 次修改操作的四个参数分别是 $(2i \bmod n)+1, (3i \bmod m)+1, n, m$。

数据范围与提示

所有测试点均满足：$1 \leq n,m \leq 10^3$，$1 \leq q \leq 10^5$。

子任务

子任务编号	约束	分值
1	$n,m \leq 2$	14
2	$q=1$	16
3	$n=1$	21
4	$n,m \leq 10$	9
5	$n,m \leq 80$	10
6	无附加约束	30