Painting the Barn (Silver)#10345
Farmer John is not good at multitasking. He often gets distracted, which makes it difficult for him to work on long-term projects. Right now, he is trying to paint one side of his barn but constantly gets distracted by tending to his cows. As a result, some parts of the wall end up with multiple layers of paint, while others remain less covered.
The side of the barn can be represented as a two-dimensional plane of size x \times y, where Farmer John sequentially applies paint in the form of rectangular areas with sides parallel to the coordinate axes. Each rectangle is defined by the coordinates of its bottom-left and top-right corners.
Farmer John wants to achieve an even coating of the wall so that he does not have to repaint it anytime soon. However, he also does not want to waste extra paint. The optimal number of layers is considered to be . Your task is to determine the area of the wall that is covered with exactly layers of paint after all rectangles have been applied.
The first line contains two integers and k~(1 \le k \le n \le 10^5) — the number of rectangles and the required number of paint layers.
Each of the following lines contains four integers x_1, y_1, x_2, y_2, defining a rectangle with its bottom-left corner at (x_1, y_1) and top-right corner at (x_2, y_2).
All coordinates and are in the range from to . All given rectangles have a positive area.
Print one integer — the area of the wall covered with exactly layers of paint.
Example 1