Counting Rectangles Drawn with Segments

Marek loves mathematics, especially geometry. One idle afternoon he grabbed his favourite ruler and drew a handful of horizontal and vertical line segments. When he looked at the paper afterwards he noticed rectangles outlined by the segments, but every time he recounted them he got a different total, so he needs your help.

You are given $N$ axis-aligned segments; each one is either horizontal (parallel to the x-axis) or vertical (parallel to the y-axis). Your task is to count how many axis-aligned rectangles are outlined by the drawn segments.

A rectangle has its left and right sides on the vertical lines $x = x_L < x_R$ and its bottom and top sides on the horizontal lines $y = y_B < y_T$. It is counted only when all four sides are completely drawn:

• the vertical segments at $x = x_L$ jointly cover the whole side from $(x_L, y_B)$ to $(x_L, y_T)$ with no gap;
• the vertical segments at $x = x_R$ jointly cover the side from $(x_R, y_B)$ to $(x_R, y_T)$;
• the horizontal segments at $y = y_B$ jointly cover the side from $(x_L, y_B)$ to $(x_R, y_B)$;
• the horizontal segments at $y = y_T$ jointly cover the side from $(x_L, y_T)$ to $(x_R, y_T)$.

A single side may be covered by the union of several collinear segments that overlap or merely touch, and segments are allowed to overlap or coincide.

The first line contains the number of segments $N$ ($4 \le N \le 800$).

Each of the next $N$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ ($-10^9 \le x_1, y_1, x_2, y_2 \le 10^9$), where $(x_1, y_1)$ is one endpoint of a segment and $(x_2, y_2)$ is the other. Every segment is parallel to the x-axis or to the y-axis.

Print a single line containing the number of rectangles.

In the first test case the rectangles split by size into four $1 \times 1$, three $2 \times 1$, two $3 \times 1$, and one $4 \times 1$, giving $4 + 3 + 2 + 1 = 10$ in total. Note that the bottom side of the widest rectangle is covered by two horizontal segments that touch, which still counts as fully drawn.