문제
Bessie의 마지막 그림이 좋은 평가를 받은 후, 그녀는 그림을 디자인하는 직업을 갖게 되었습니다. 그녀는 두 면이 동일선상에 있지 않은 좌표축과 평행한 4면이 있는 평면에서 1≤N≤105개의 직사각형을 선택하여 그림을 디자인합니다. 이 직사각형의 경계는 그림의 칠해진 영역의 경계를 정의합니다.
전위 예술가인 Bessie는 그림이 홀스타인 소를 닮았어야 한다고 생각했습니다. 보다 구체적으로, 이러한 직사각형으로 구성된 각 영역은 검은색 또는 흰색으로 표시되고 인접한 두 영역은 동일한 색상으로 표시되지 않으며 직사각형 외부의 모든 영역은 흰색으로 표시됩니다.
직사각형이 선택된 상태에서 Bessie는 매개변수 T에 따라 다음 중 하나를 출력할 것으로 예상합니다.
T=1이면 전체 영역 수를 출력합니다.
T=2이면 흰색 영역의 개수와 검은색 영역의 개수를 출력합니다.
입력
입력의 첫 번째 줄에는 N과 T가 포함됩니다.
다음 N 줄은 각각 (x1, y1), (x2, y2) 형식의 직사각형을 나타냅니다. 여기서 1 ≤ x1 < x2 ≤ 2N 및 1 ≤ y1 < y2 ≤ 2N입니다. (x1, y1) 및 (x2, y2)는 각각 사각형의 왼쪽 아래 모서리와 오른쪽 위 모서리입니다.
입력은 모든 xi가 1 … 2N의 순열을 구성하고 모든 yi가 1 … 2N의 순열을 구성함을 보장합니다.
출력
T=1이면 정수를 출력하고, 그렇지 않으면 원하는 답을 나타내는 두 개의 공백으로 구분된 정수를 출력합니다.
예제1
입력
2 1
1 1 3 3
2 2 4 4
출력
4
예제2
입력
5 2
1 5 3 6
5 4 7 9
4 1 8 3
9 8 10 10
2 2 6 7
출력
4 5
힌트
출처
USACO 2022 February Platinum