Area and Perimeter of a Union of Rectangles

Time limit1sMemory limit128 MB

Summary

Given up to 10000 axis-parallel rectangles on an integer grid, compute the area of their union (and its perimeter when r=2), counting overlaps once.

Level: Hard8 of 10
Topics: Segment tree, Sorting, Prefix sum, Geometry
Solved: No attempts yet

Problem

Several rectangular sheets are placed on a plane. Write a program that computes the area, or the perimeter, of the region covered by these sheets.

Regarding the plane as a coordinate plane, the sheets are arranged so that the following two conditions hold.

The $x$ and $y$ coordinates of the four vertices of every sheet (rectangle) are integers between $0$ and $10000$ inclusive, and each side of every rectangle is parallel to the $x$ -axis or the $y$ -axis.
The number of sheets is at most $10000$ .

Sheets may overlap one another; overlapping area is counted only once. The perimeter is the total length of the boundary of the covered region, including the boundary of any hole that appears inside it.

Input

The first line contains the number of rectangles $n$ and an integer $r$ indicating the query type, separated by a space. Each of the next $n$ lines contains the lower-left vertex $(x_1, y_1)$ and the upper-right vertex $(x_2, y_2)$ of a sheet, given in the order $x_1$ , $y_1$ , $x_2$ , $y_2$ and separated by spaces.

Output

If $r = 1$ , print the area of the covered region on the first line. If $r = 2$ , print the area on the first line and the perimeter on the second line. In either case, end the output with a newline.

Examples4

Example 1

Input

Expected output

Example 2

Input

Expected output

29
38

Example 3
Input
```
2 2
0 0 8 9
0 0 9 8
```
Expected output
```
80
36
```
Example 4
Input
```
3 2
2 2 8 8
3 0 4 9
5 0 7 9
```
Expected output
```
45
36
```