摊位大作战

题目描述

学校有一块 2000×2000 的正方形操场，划分成一个个边长为1米的小方块，每个小方块的位置用坐标 $(r,c)$ 表示——其中 $r$ 是行数（从上往下），$c$ 是列数（从左往右）。

$N$ 个社团申请了摊位，编号从 $1$ 到 $N$。第 $i$ 个社团的摊位占据矩形区域：所有满足 $U_i \le r \le D_i$ 且 $L_i \le c \le R_i$ 的小方块。

对于每个社团 $k$（$k=1,2,\dots,N$），计算：

• 临时取消第 $k$ 个社团的摊位后，剩下 $N-1$ 个社团占据的小方块总数
• 用操场总面积减去被占据的小方块数，得到 空闲小方块的数量

输入格式

第一行输入一个整数 $N（1 \le N \le 2 \times 10^5）$，表示社团的数量。 接下来 $N$ 行，每行输入四个整数 $U_i$、$D_i$、$L_i$、$R_i$（$1 \le U_i \le D_i \le 2000$，$1 \le L_i \le R_i \le 2000$），表示第 $i$ 个社团摊位的矩形区域。

输出格式

输出共 $N$ 行，每行一个整数，表示取消第 $k$ 个社团摊位后操场中剩下的空闲小方块数量。

样例 1

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

提示

我们可以先看操场左上角 5×6 的一小块区域（对应原题的示意图）：

• 原本的5个社团摊位在这块小区域里各有重叠。
• 当取消第1个社团的摊位时，剩下4个社团一共占了17个小方块；操场总面积是 $2000 \times 2000 = 4000000$，所以空闲数量就是 $4000000 - 17 = 3999983$。
• 当取消第2个社团的摊位时，剩下4个社团一共占了24个小方块，空闲数量就是 $4000000 - 24 = 3999976$。
• 其余情况以此类推。