← 返回题目列表

Codeforces · 610/D

D. Vika 和片段

中文机器翻译题面 查看原题

维卡有一张无限大的方格纸。最初所有方块都是白色的。她在这张纸上引入了一个二维坐标系,并画了n条与坐标轴平行的黑色水平和垂直线段。所有线段的宽度都等于 1 个正方形,这意味着每个线段占据一行或一列中的一组相邻正方形。

您的任务是计算绘制的单元格的数量。如果一个单元格被绘制多次,则应该只计算一次。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — Vika 绘制的线段数。

接下来的 n 行中的每一行都包含四个整数 x1、y1、x2 和 y2 (- 109 ≤ x1, y1, x2, y2 ≤ 109)——Vika 绘制的线段端点的坐标。保证所有线段与坐标轴平行。片段可能接触、重叠,甚至完全重合。

输出

打印 Vika 绘制的单元格数量。如果某个单元格被绘制多次,则应在答案中精确计算一次。

示例

输入 #1

3
0 1 2 1
1 4 1 2
0 3 2 3

输出 #1

8

输入 #2

4
-2 -1 2 -1
2 1 -2 1
-1 -2 -1 2
1 2 1 -2

输出 #2

16

注意

在第一个示例中,Vika 将绘制正方形 (0, 1)、(1, 1)、(2, 1)、(1, 2)、(1, 3)、(1, 4)、(0, 3) 和 (2, 3)。