Description

Write a program to compute the perimeter.

The $7$ rectangles are shown in Figure 1.

The boundary of the union of all rectangles is shown in Figure 2.

All rectangle vertices have integer coordinates.

Input Format

The first line of the input contains an integer $N$, the number of rectangles. Each of the next $N$ lines gives the coordinates of the lower-left corner and the upper-right corner of a rectangle.

Output Format

Output a single positive integer, the perimeter of the union of all rectangles.

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

228

Hint

Constraints

For all testdata, $1 \le N < 5000$, and all coordinate values are in the range $-10^4$ to $10^4$.

Translated by ChatGPT 5