题目描述

天空被表示为一个 $2000 \times 2000$ 的网格。
仰望天空时，从上往下第 $r$ 行、从左往右第 $c$ 列的格子称为 $(r,c)$。

现在天空中有编号为 $1,2,\dots,N$ 的 $N$ 朵云。
如果一个格子 $(r,c)$ 满足 $U_i \le r \le D_i$ 且 $L_i \le c \le R_i$，则该格子被第 $i$ 朵云覆盖。

对于 $k=1,2,\dots,N$，请回答下列问题：

• 将第 $k$ 朵云从 $N$ 朵云中移除。此时天空中还剩 $N-1$ 朵云。现在有多少格子没有被任何云覆盖？

输入格式

输入从标准输入中给出，格式如下：

$N$
$U_1$ $D_1$ $L_1$ $R_1$
$U_2$ $D_2$ $L_2$ $R_2$
$\vdots$
$U_N$ $D_N$ $L_N$ $R_N$

输出格式

输出共 $N$ 行。
第 $i$ 行输出在移除第 $i$ 朵云时，未被任何云覆盖的格子的数量。

5
2 4 1 4
3 3 3 5
1 3 4 6
4 5 3 5
5 5 4 6

3999983
3999976
3999982
3999978
3999977

说明/提示

样例说明 1

下图展示了天空左上角 $5 \times 6$ 的区域。

• 当移除第 1 朵云时，被至少一朵云覆盖的格子有 $17$ 个，所以未被覆盖的格子有 $3999983$ 个。
• 当移除第 2 朵云时，被至少一朵云覆盖的格子有 $24$ 个，所以未被覆盖的格子有 $3999976$ 个。
• 当移除第 3 朵云时，被至少一朵云覆盖的格子有 $18$ 个，所以未被覆盖的格子有 $3999982$ 个。
• 当移除第 4 朵云时，被至少一朵云覆盖的格子有 $22$ 个，所以未被覆盖的格子有 $3999978$ 个。
• 当移除第 5 朵云时，被至少一朵云覆盖的格子有 $23$ 个，所以未被覆盖的格子有 $3999977$ 个。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le U_i \le D_i \le 2000$
• $1 \le L_i \le R_i \le 2000$
• 所有输入均为整数。