对于一个 $n \times m$ 的 01 矩阵 $A$（下标从 1 开始，下同），定义一个 $n \times m$ 的 01 矩阵 $B$ 是好的当且仅当：

1. 对于第 $i \;(1 \le i \le n)$ 行，不存在 $1 \le j,k \le m, j \neq k$ 同时满足： $$ A_{i,j} = B_{i,k} = 1, \quad A_{i,k} = B_{i,j} = 0 $$

2. 对于第 $i \;(1 \le i \le m)$ 列，不存在 $1 \le j,k \le n, j \neq k$ 同时满足： $$ A_{j,i} = B_{j,i} = 1, \quad A_{k,i} = B_{k,i} = 0 $$

初始 $B$ 矩阵所有位置为 0，每次可以选择若干个位置，将它们同时变成 1。要求做完操作后，矩阵 $B$ 仍然是好的。设最多执行 $k$ 次操作，则矩阵 $A$ 的权值为 $k$。

小 █ 现在有一个 $N \times N$ 的 01 矩阵 $M$。由于 $N$ 很大，所以 $M$ 由特殊方式生成。

初始 $M$ 中所有位置均为 0，有 $Q$ 次修改操作。每次操作给定 $x_1, x_2, y_1, y_2$，对于满足 $x_1 \le i \le x_2$ 且 $y_1 \le j \le y_2$ 的所有位置 $(i, j)$，将 $M_{i,j}$ 变为 $1 - M_{i,j}$。

定义 $S_{i,j}$ 为 $M$ 前 $i$ 行前 $j$ 列构成的子矩阵的权值。

输入格式

第一行三个数 $N, Q, op$。

接下来 $Q$ 行，每行四个数 $x_1, x_2, y_1, y_2$。

输出格式

若 $op = 0$，输出一个数 $S_{N,N}$。

若 $op = 1$，输出一行 $N$ 个数，分别是 $S_{N,1}, S_{N,2}, \cdots, S_{N,N}$。

输入输出样例

样例输入 1

2 2 1
1 1 1 1
2 2 2 2

样例输出 1

2 1

样例 2 & 3

详见下发文件。

数据范围

• 特殊性质 A：保证 $op = 0$。
• 特殊性质 B：一次操作的代价为 $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$，所有操作的代价之和 $\le 2 \times 10^6$。

对于所有数据，保证： $$ 1 \le N, Q \le 2 \times 10^5, \quad 1 \le x_1 \le x_2 \le N, \quad 1 \le y_1 \le y_2 \le N, \quad op \in \{0, 1\} $$