포스터

알고리즘 대통령을 뽑는 선거가 열린다. 출마 자격에 제한이 없어서 후보가 아주 많고, 홍보 경쟁도 그만큼 치열하다.

가장 큰 골칫거리는 포스터다. 후보는 저마다 자신을 홍보하는 직사각형 포스터를 한 장씩 들고 나와 거리의 벽에 붙인다. 크기가 제각각인 포스터가 벽을 뒤덮고, 남의 포스터에 가려진 후보가 그 위에 다시 붙이는 일이 반복되자 선거관리위원회가 규칙을 정했다.

후보 $N$명은 1번부터 $N$번까지 서로 다른 번호를 받는다. 각 후보는 벽에 포스터를 한 장만 붙이고, 붙이는 순서는 번호 순서와 같다. 즉 번호가 큰 후보의 포스터가 이미 붙어 있던 포스터를 덮는다.

벽은 2차원 좌표평면으로 볼 수 있을 만큼 크다. $N$명이 모두 포스터를 붙인 뒤 벽을 정면에서 봤을 때, 후보마다 자기 포스터가 보이는 넓이를 구하자.

첫째 줄에 후보의 수 $N$ ($1 \le N \le 5000$)이 주어진다.

둘째 줄부터 $N$개의 줄에 1번 후보부터 $N$번 후보까지의 포스터 정보가 한 줄에 하나씩 주어진다. 각 줄은 네 정수 $x_1$, $y_1$, $x_2$, $y_2$로 이루어지며, 왼쪽 아래 꼭짓점이 $(x_1, y_1)$이고 오른쪽 위 꼭짓점이 $(x_2, y_2)$인 직사각형 포스터를 그 자리에 붙인다는 뜻이다. $x_1 < x_2$, $y_1 < y_2$이고, 네 좌표는 모두 $-10^9$ 이상 $10^9$ 이하의 정수다.

$N$개의 줄을 출력한다. $i$번째 줄에는 $i$번 후보의 포스터가 보이는 넓이를 출력한다.

아래 그림은 첫 번째 예제를 그린 것이다.

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