题目描述

在平面内有一些矩形，它们的两条边都平行于坐标轴。

我们称一个点被某个矩形覆盖，是指这个点在矩形的内部或者边界上。

请问，被奇数个矩形覆盖和被偶数 $(\geq 2)$ 个矩形覆盖的点的面积分别是多少?

输入格式

输入的第一行包含一个整数 $n$，表示矩形的个数。

接下来 $n$ 行描述这些矩形，其中第 $i$ 行包含四个整数 $l_{i}, b_{i}, r_{i}, t_{i}$，表示矩形的两个对角坐标分别为 $\left(l_{i}, b_{i}\right),\left(r_{i}, t_{i}\right)$ 。

输出格式

输出两行。

第一行包含一个整数，表示被奇数个矩形覆盖的点的面积。

第二行包含一个整数，表示被偶数 $(\geq 2)$ 个矩形覆盖的点的面积。

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

8
2

提示

对于 $20 \%$ 的评测用例, $1 \leq n \leq 10,0 \leq l_{i}<r_{i} \leq 100,0 \leq b_{i}<t_{i} \leq 100$ 。

对于 $40 \%$ 的评测用例, $1 \leq n \leq 1000,0 \leq l_{i}<r_{i} \leq 100,0 \leq b_{i}<t_{i} \leq 100$ 。

对于 $60 \%$ 的评测用例, $1 \leq n \leq 10000,0 \leq l_{i}<r_{i} \leq 1000,0 \leq b_{i}<t_{i} \leq 1000$ 。

对于 $80 \%$ 的评测用例, $1 \leq n \leq 10^5,0 \leq l_{i}<r_{i} \leq 10^5,0 \leq b_{i}<t_{i} \leq 10^5$。

对于所有评测用例, $1 \leq n \leq 10^5,0 \leq l_{i}<r_{i} \leq 10^{9}, 0 \leq b_{i}<t_{i} \leq 10^{9}$。

蓝桥杯 2020 年国赛 A 组 I 题。