{"raw_statement":[{"iden":"statement","content":"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.\n\nDreamoon'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.\n\nNow, 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.\n\nThe 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 xi1, yi1, xi2, yi2, denoting that the i-th segment Dreamoon drew is a straight line segment between points (xi1, yi1) and (xi2, yi2).\n\nOutput one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew.\n\n"},{"iden":"input","content":"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 xi1, yi1, xi2, yi2, denoting that the i-th segment Dreamoon drew is a straight line segment between points (xi1, yi1) and (xi2, yi2).  1 ≤ N ≤ 2 × 103  0 ≤ xi1, yi1, xi2, yi2 ≤ 2 × 103  the lengths of all line segments in input are non-zero "},{"iden":"output","content":"Output one integer on a single line: how many grid squares are crossed by at least one of the line segments which Dreamoon drew."},{"iden":"examples","content":"Input30 0 5 50 5 5 00 5 5 0Output9Input10 0 4 3Output6Input20 0 4 31 0 3 3Output6"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of line segments.  \nFor each $ i \\in \\{1, \\dots, N\\} $, let $ L_i $ be a line segment defined by endpoints $ (x_{i1}, y_{i1}) $ and $ (x_{i2}, y_{i2}) $, where $ x_{ij}, y_{ij} \\in [0, 2000] \\cap \\mathbb{Z} $.\n\nLet $ \\mathcal{S} = \\{ [a, a+1] \\times [b, b+1] \\mid a, b \\in \\{0, 1, \\dots, 1999\\} \\} $ be the set of all unit grid squares in the $ 2000 \\times 2000 $ grid.\n\n**Constraints**  \n1. $ 1 \\le N \\le 1000 $  \n2. For each $ i $, $ 0 \\le x_{i1}, y_{i1}, x_{i2}, y_{i2} \\le 2000 $  \n\n**Objective**  \nCompute the cardinality of the set:  \n$$\n\\left| \\left\\{ S \\in \\mathcal{S} \\mid \\exists\\, i \\in \\{1, \\dots, N\\} \\text{ such that } L_i \\cap \\text{int}(S) \\neq \\emptyset \\right\\} \\right|\n$$  \nwhere $ \\text{int}(S) $ denotes the interior of square $ S $.","simple_statement":"Count how many unit squares are crossed by at least one of the given line segments on a 2000×2000 grid.","has_page_source":false}