403656: GYM101234 C Crazy Dreamoon

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] × [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 × 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, to cross a square, a segment must contain an interior point of the 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).

• 1 ≤ N ≤ 2 × 10³
• 0 ≤ x_i1, y_i1, x_i2, y_i2 ≤ 2 × 10³
• the lengths of all line segments in input are non-zero

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

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

9

1
0 0 4 3

6

2
0 0 4 3
1 0 3 3

6