955. Rectangle Area II — Coordinate Compression

Given a list of axis-aligned rectangles, each as [x1, y1, x2, y2] (bottom-left and top-right corners), return the total area covered by their union, modulo 1,000,000,007. Overlapping regions are counted once. The input is a JSON array of rectangles.

Input: A JSON array of rectangles.

Output: Integer — the total covered area mod 1e9+7.

Examples

Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: Union area is 6.

Input: [[0,0,1,1],[2,2,3,3]]
Output: 2
Explanation: Two disjoint unit squares.

Input: [[0,0,1,1]]
Output: 1
Explanation: Single rectangle.

Constraints

• 1<=rectangles<=200
• 0<=coordinate<=10^9

Asked by