13167번 - 포스터

2016년 8월 20일, 알고리즘 대통령을 뽑는 선거가 있다. 이 선거는 알고리즘계의 정상을 노리는 사람이라면 누구나 출마할 수 있다. 특히 올해에는 갑작스러운 알고리즘 붐으로 그 출마자의 수가 월등히 많아 홍보 기간부터 치열한 경쟁이 일고 있다.

그중 가장 문제가 되는 것은 포스터다. 출마자들은 모두 자신을 홍보하는 직사각형 모양의 포스터가 하나씩 있는데, 이 포스터가 크기도 제각각인 데다 그 수도 많아서 거리의 벽이 온통 포스터로 도배되어버렸다. 다른 출마자의 포스터로 인해 자신의 포스터가 가려지면 그 위에 다시 붙이는 등 여러 문제가 발생하자 UCPC(Ultra Capsyong Prominent Center of Algorithm)가 이를 규제하기 위해 나섰다.

총 N명의 출마자에게 각자 1번부터 N번까지의 서로 다른 후보 번호가 주어진다. 각 출마자는 한 벽에 한 장씩, 1번부터 후보 번호의 순서대로 벽에 포스터를 붙이게 된다. 나중에 붙인 출마자의 포스터가 이전에 붙여져 있던 포스터를 덮을 수 있다.

2차원 좌표계로 나타낼 수 있는 아주 큰 벽이 있다. 이 벽면에 N명의 출마자가 모두 포스터를 붙인 뒤 벽면을 바라봤을 때 각 출마자별로 출마자의 포스터가 보이는 넓이를 계산하자.

첫 번째 줄에는 출마자의 수 N (1 ≤ N ≤ 5,000)이 주어진다. 두 번째 줄부터 N개의 줄에는 1번부터 N번 후보의 포스터 정보가 한 줄 씩 주어진다. 포스터 정보는 4개의 정수 x₁,y₁,x₂,y₂로 이루어지며, 이는 좌측 하단 (x₁, y₁)부터 우측 상단 (x₂, y₂)까지의 공간을 차지하는 포스터를 해당 좌표 범위에 붙인다는 의미이다(x₁ < x₂,  y₁ < y₂). 각 좌표의 범위는 -1,000,000,000보다 크거나 같고, 1,000,000,000보다 작거나 같다.

1번 후보부터 N번 후보의 포스터가 보이는 넓이를 줄로 구분하여 총 N개의 줄에 출력한다.

• 1번 후보자 : 파란색 포스터 / 2번 후보자 : 초록색 포스터
• 3번 후보자 : 주황색 포스터 / 4번 후보자 : 노란색 포스터