题目描述

平面上摆放着 $n$ 个四边都与坐标轴平行的矩形，它们可能互相重叠。请求出这些矩形的并集所覆盖的总面积。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，每行四个非负整数 $x_1, y_1, x_2, y_2$，表示一个矩形的四个顶点坐标分别为 $(x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)$。

输出格式

一行一个整数，表示 $n$ 个矩形的并集覆盖的总面积。

样例

2
100 100 200 200
150 150 250 255

18000

提示

对于 $20\%$ 的数据，$1 \le n \le 1000$。

对于 $100\%$ 的数据，$1 \le n \le {10}^5$，$0 \le x_1 \lt x_2 \le {10}^9$，$0 \le y_1 \lt y_2 \le {10}^9$。