Page not loading? Try clicking here.
Placeholder

#1568

직사각형 3s 1024MB

Problems

평면에 축에 평행한 직사각형이 N개 주어진다.

이들이 차지하는 면적을 구하는 프로그램을 작성하시오.


Input

첫 행에 자연수 N이 주어진다. (1 ≤ N ≤ 200,000)

이어서 N개의 행에 사각형을 나타내는 좌표 x1, x2, y1, y2가 공백을 구분하여 주어진다. 

(0 \le x_1 < x_2 ≤ 10^9), (0 ≤ y_1 < y_2 ≤ 10^9)


Output

N개의 사각형이 차지하는 면적을 출력한다.

여러 번 겹치는 영역의 경우 한 번만 면적에 포함된다.


Example #1

2

0 3 1 2

1 2 0 3
5

Example #2

4
2 3 1 3
1 3 0 4
0 4 1 5
2 4 2 5
18


Source

MIT Programming Contest Team Contest 1 2008 7번

You must sign in to write code.