A zoning map has n axis-aligned rectangles on an integer grid. Each rectangle is given by its lower-left corner (x1, y1) and upper-right corner (x2, y2) with x1 < x2 and y1 < y2. Two rectangles conflict when the region they share has strictly positive area (merely touching along an edge or corner is not a conflict). Count the number of unordered pairs of rectangles that conflict.
Input format
Line 1: an integer n, the number of rectangles.
Next n lines: four integers x1 y1 x2 y2 describing a rectangle.
Output format
A single integer: the number of conflicting pairs.
Constraints
- 1 <= n <= 2000
- -1000000000 <= x1 < x2 <= 1000000000
- -1000000000 <= y1 < y2 <= 1000000000