Problem Description

There is a grid of size $10^9 \times 10^9$. Let the square at the $i$-th row from the top and the $j$-th column from the left be denoted as $(i, j)$. Each square in the grid is either white or black. Initially, all squares are white.

Takahashi will now stamp the grid a total of $N$ times. For the $i$-th ($1 \leq i \leq N$) stamping, he will use a rectangular stamp of size $H_i \times W_i$ and place it such that its top-left corner coincides with $(R_i, C_i)$ (the part of the stamp that is stamped will not extend beyond the grid). This stamp is designed such that when stamped on a completely white grid, it creates a checkered pattern. The square stamped at the $p$-th row from the top and the $q$-th column from the left of the stamp ($1 \leq p \leq H_i, 1 \leq q \leq W_i$) will invert its color if $p + q$ is even, and remain unchanged if $p + q$ is odd.

After stamping the grid $N$ times, count how many black squares there are.

Input Format

The input is given from the standard input in the following format:

$N$ $H_1$ $W_1$ $R_1$ $C_1$ : $H_N$ $W_N$ $R_N$ $C_N$

Output Format

Output the number of black squares after stamping the grid $N$ times.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

5
66518928 212072708 158598694 334005903
54102801 860639145 839206374 16401163
226949335 660240556 476286324 65656871
153262413 54385827 719562883 5920096
496820604 90893558 460217283 428740659

Sample Output #2

130526013386872287

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq H_i \leq 10^9$
• $1 \leq W_i \leq 10^9$
• $1 \leq R_i \leq 10^9$
• $1 \leq C_i \leq 10^9$
• $H_i + R_i - 1 \leq 10^9$
• $W_i + C_i - 1 \leq 10^9$
• All inputs are integers

Sample Explanation 1

The image below shows the changes in the top-left $3 \times 3$ squares of the grid.

见题面 Input 部分

见题面 Output 部分