给定一个包含 $n$ 行 $m$ 列的矩阵 $A$，其中包含 $nm$ 个格子，每个格子可以填入 0 或 1。行从上到下编号为 $1, \dots, n$，列从左到右编号为 $1, \dots, m$。第 $i$ 行第 $j$ 列的格子（其中 $1 \le i \le n, 1 \le j \le m$）坐标为 $(i, j)$。

我们可以在矩阵上执行对选定矩形区域内数字进行取反（negation）的操作。每次操作由四个数字 $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。随后执行 $q$ 次操作，每次操作都会改变矩阵。在执行完每次操作后，我们想知道，为了使矩阵中所有数字重新变回 0，最少还需要执行多少次简单操作。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n, m \le 1000, 1 \le q \le 100\,000$)，分别表示矩阵的维度和操作次数。

接下来的 $q$ 行，每行包含四个整数 $i_1, j_1, i_2, j_2$ ($1 \le i_1 \le i_2 \le n, 1 \le j_1 \le j_2 \le m$)，描述一次操作。

输出格式

输出共 $q$ 行，每行包含一个整数。对于第 $i$ 次操作，输出在执行完前 $i$ 次操作后，为了使矩阵 $A$ 中的所有数字变为 0，所需的最少简单操作次数。

样例

输入 1

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

输出 1

2
1
3

子任务

测试集分为以下子任务。每个子任务的测试用例由一组或多组独立的测试组组成。