최대 100개의 축에 평행한 직사각형이 주어질 때, 모든 직사각형의 합집합 넓이를 구한다.
상현이는 입대를 앞두고 이별 파티를 열려고 한다. 파티를 치를 행사장을 대여하는데, 이 업체는 전직 프로그래머만 일해서 대여 방식이 독특하다.
상현이가 빌릴 장소를 정하면 업체는 그 장소를 남김없이 덮는 직사각형 NNN개를 만든다. 그리고 직사각형의 개수 NNN과 각 직사각형의 좌측 하단 좌표, 우측 상단 좌표를 알려준다. NNN개의 직사각형은 일부만 겹칠 수도 있고 완전히 겹칠 수도 있다. 모든 직사각형의 변은 좌표축과 평행하다.
상현이가 빌린 행사장의 넓이, 즉 NNN개의 직사각형 중 적어도 하나가 덮는 영역의 넓이를 구하는 프로그램을 작성하라.
첫째 줄에 직사각형의 개수 NNN(2≤N≤1002 \le N \le 1002≤N≤100)이 주어진다.
이어지는 NNN개의 줄에 네 정수 x1x_1x1, y1y_1y1, x2x_2x2, y2y_2y2(0≤x1<x2≤5000 \le x_1 < x_2 \le 5000≤x1<x2≤500, 0≤y1<y2≤5000 \le y_1 < y_2 \le 5000≤y1<y2≤500)가 공백으로 구분되어 주어진다. 각 직사각형의 좌측 하단 좌표는 (x1,y1)(x_1, y_1)(x1,y1)이고, 우측 상단 좌표는 (x2,y2)(x_2, y_2)(x2,y2)이다.
첫째 줄에 상현이가 빌린 행사장의 넓이를 출력한다. 넓이는 항상 정수이므로 소수점 없이 출력한다.