For an $n \times m$ 01 matrix $A$ (using 1-based indexing), a 01 matrix $B$ of the same dimensions is defined as "good" if and only if:

1. For each row $i \;(1 \le i \le n)$, there do not exist $1 \le j, k \le m$ with $j \neq k$ such that: $$ A_{i,j} = B_{i,k} = 1, \quad A_{i,k} = B_{i,j} = 0 $$

2. For each column $i \;(1 \le i \le m)$, there do not exist $1 \le j, k \le n$ with $j \neq k$ such that: $$ A_{j,i} = B_{j,i} = 1, \quad A_{k,i} = B_{k,i} = 0 $$

Initially, all entries in matrix $B$ are 0. In each step, you can choose a set of positions and flip them to 1 simultaneously. The requirement is that after the operation, matrix $B$ must remain good. The weight of matrix $A$ is defined as the maximum number of operations $k$ required.

Xiao █ has an $N \times N$ 01 matrix $M$. Since $N$ is very large, $M$ is generated in a special way.

Initially, all positions in $M$ are 0. There are $Q$ modification operations. Each operation is given by $x_1, x_2, y_1, y_2$, where for all positions $(i, j)$ such that $x_1 \le i \le x_2$ and $y_1 \le j \le y_2$, $M_{i,j}$ is changed to $1 - M_{i,j}$.

Define $S_{i,j}$ as the weight of the submatrix formed by the first $i$ rows and the first $j$ columns of $M$.

Input

The first line contains three integers $N, Q, op$.

The next $Q$ lines each contain four integers $x_1, x_2, y_1, y_2$.

Output

If $op = 0$, output a single integer $S_{N,N}$.

If $op = 1$, output $N$ integers in a single line, representing $S_{N,1}, S_{N,2}, \cdots, S_{N,N}$.

Examples

Input 1

2 2 1
1 1 1 1
2 2 2 2

Output 1

2 1

Note 2 & 3

See the provided files.

Constraints

• Special Property A: Guaranteed $op = 0$.
• Special Property B: The cost of one operation is $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$, and the sum of costs of all operations is $\le 2 \times 10^6$.

For all data, it is guaranteed that: $$ 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\} $$