시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 133 25 16 15.842%

문제

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개의 정수 x1,y1,x2,y2로 이루어지며, 이는 좌측 하단 (x1, y1)부터 우측 상단 (x2, y2)까지의 공간을 차지하는 포스터를 해당 좌표 범위에 붙인다는 의미이다(x1 < x2,  y1 < y2). 각 좌표의 범위는 -1,000,000,000보다 크거나 같고, 1,000,000,000보다 작거나 같다.

출력

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

예제 입력

4
0 0 8 7
2 3 11 11
5 1 10 6
1 4 7 8

예제 출력

23
41
21
24

힌트

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