1295번 - 평면도

건축회사 “네모”는 사각형을 주제로 건물을 설계하는 회사로 유명하다. 현재 “네모”에서 설계하고 있는 건물의 각 층의 외벽은 직사각형으로 만들어져 있으며, 각 층의 내부 사무실은 여러 개의 직사각형을 외벽의 내부에 그렸을 때 만들어지는 도형으로 설계하고 있다.

예를 들어, 아래 <그림 1>은 이런 방법으로 설계된 건물의 어떤 층의 평면도를 나타낸다. 이 평면도의 가장 바깥 사각형은 그 층의 외벽을 나타내는 사각형이며, 그 내부는 그림에서와 같이 네 개의 사각형에 의하여 7개의 사무실로 나누어져 있다.

<그림 1>

각 건물 층의 외벽을 나타내는 사각형과 그 내부 사무실을 설계할 여러 개의 사각형이 주어졌을 때, 이 평면도에서 만들어지는 사무실의 개수와 가장 큰 사무실의 크기를 계산하는 프로그램을 작성하시오. 단, 모든 사각형의 변은 좌표축에 평행하다고 가정한다.

예를 들어, 위 <그림 1>과 같은 설계도에 의하여 만들어진 사무실 중에서 가장 큰 사무실의 공간은 <그림 2>에서 빗금으로 표시된 공간이다.

<그림 2>

첫째 줄에 사각형의 개수 N (2 ≤ N ≤ 50,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 사각형의 왼쪽 위 꼭짓점의 좌표와 오른쪽 아래 꼭짓점의 좌표를 나타내는 네 개의 정수 x1, y1, x2, y2(0 ≤ x1 < x2 ≤ 1,000,000,000, 0 ≤ y2 < y1 ≤ 1,000,000,000)가 주어진다. 사각형의 왼쪽 위 꼭짓점의 좌표는 (x1, y1)이며, 오른쪽 아래 꼭짓점의 좌표는 (x2, y2)이다. 입력에서 주어지는 사각형 중의 하나는 다른 모든 사각형을 포함하는 외벽을 나타내는 사각형이다. 모든 사각형의 꼭짓점의 x-좌표는 서로 다르며, 또한 y-좌표도 서로 다르다.

첫째 줄에 입력에서 주어진 사각형에 의하여 만들어지는 사무실의 개수와 가장 큰 사무실의 크기를 나타내는 두 개의 정수를 한 개의 빈칸을 사이에 두고 출력한다. 사무실의 개수는 1,000,000개 이하이며 가장 큰 사무실의 크기는 4,200,000,000 이하이다.