시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB222100.000%

문제

Dreamoon likes algorithm competitions very much. But 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 Cartesian coordinate system with range $[0, 2000] \times [0, 2000]$ for the coordinates. 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. Please help Dreamoon find the answer. Note that touching an edge of a grid square is not considered as crossing this square.

입력

The first line of input contains an integer $N$ denoting the number of lines Dreamoon draw. The $i$-th line of 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 one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.

제한

  • $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

예제 입력 1

3
0 0 5 5
0 5 5 0
0 5 5 0

예제 출력 1

9

예제 입력 2

1
0 0 4 3

예제 출력 2

6

예제 입력 3

2
0 0 4 3
1 0 3 3

예제 출력 3

6