Area Covered by Sticky Notes

Sticky notes lie scattered on a desk, overlapping each other. Each note is a rectangle with its sides parallel to the edges of the desk, given as a tuple (x1, y1, x2, y2) of integers: (x1, y1) is its bottom-left corner and (x2, y2) its top-right corner, with x1 <= x2 and y1 <= y2.

Write covered_area(rects) that returns the total area of the desk covered by at least one note, as an integer. Where notes overlap, that part counts once. A note with zero width or zero height covers nothing.

Examples

covered_area([(0, 0, 2, 2), (1, 1, 3, 3)])                # returns 7
covered_area([(0, 0, 4, 4), (1, 1, 2, 2)])                # returns 16
covered_area([(0, 0, 1, 1), (2, 0, 3, 1), (0, 0, 3, 1)])  # returns 3
covered_area([])                                          # returns 0

In the first example each note covers 4, and they share a 1 by 1 square, so the total is 4 + 4 - 1 = 7.

Constraints

• 0 to 200 notes.
• Coordinates are integers between -109 and 109, far too large to count the covered squares one by one.