Crazy Dreamoon

Time limit1sMemory limit512 MB

Summary

Given up to 2000 line segments in a 2000 by 2000 grid, count the grid squares whose interior is crossed by at least one segment.

Level: Hard8 of 10
Topics: Geometry, Math, Implementation, Sorting
Solved: No attempts yet

Problem

Dreamoon likes algorithm competitions very much. When he feels crazy because he cannot figure out any solution for any problem in a competition, he often draws many meaningless straight line segments on his calculation paper.

Dreamoon's calculation paper is special. It can be imagined as the plane with a Cartesian coordinate system where the coordinates range over $[0, 2000] \times [0, 2000]$ . The grid lines are all lines of the form $x = c$ or $y = c$ for every integer $c$ between $0$ and $2000$ , inclusive. So the grid contains $2000 \times 2000$ squares.

Now Dreamoon wonders how many grid squares are crossed by at least one of the lines he drew. Help Dreamoon find the answer. Touching an edge of a grid square is not considered as crossing this square.

Input

The first line of input contains an integer $N$ denoting the number of lines Dreamoon drew. The $i$ -th line of the following $N$ lines contains four integers $x_{i1}, y_{i1}, x_{i2}, y_{i2}$ , denoting that the $i$ -th segment Dreamoon drew is a straight line segment between points $(x_{i1}, y_{i1})$ and $(x_{i2}, y_{i2})$ .

Output

Output one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.

Constraints

$1 \le N \le 2 \times 10^3$
$0 \le x_{i1}, y_{i1}, x_{i2}, y_{i2} \le 2 \times 10^3$
the lengths of all line segments in input are non-zero

Examples3

Example 1
Input
```
3
0 0 5 5
0 5 5 0
0 5 5 0
```
Expected output
```
9
```
Example 2
Input
```
1
0 0 4 3
```
Expected output
```
6
```
Example 3
Input
```
2
0 0 4 3
1 0 3 3
```
Expected output
```
6
```