32171번 - 울타리 공사

문제

푸앙 마을은 학점이라는 위협으로부터 마을을 보호하기 위해 마을 외곽에 울타리를 설치한다.

건물은 2차원 평면상에서 $(a_i, b_i)$를 왼쪽 아래 꼭짓점, $(c_i, d_i)$를 오른쪽 위 꼭짓점으로 하는 직사각형으로 표현된다. 푸앙 마을은 세계 제일 건축 기술을 가지고 있기 때문에 건물을 겹쳐서 지을 수 있다. 울타리는 푸앙 마을에 존재하는 모든 건물을 감싸는 최소 둘레의 직사각형으로 설치된다. 이때 직사각형의 변은 $x$축 혹은 $y$축에 평행해야 한다. 울타리를 설치하는 데 드는 비용은 울타리의 둘레 길이가 된다.

울타리는 튼튼해야 한다는 푸앙 마을의 철칙에 따라, 울타리 공사를 할 때마다 기존 울타리는 모두 철거하고 새로 울타리를 설치한다. 건물이 하나도 없는 상태에서 $N$개의 건물을 건설하고자 한다. 건물 한 채를 건설할 때마다 울타리 공사 시에 드는 비용을 출력해 보자.

입력

첫 번째 줄에 건설하고자 하는 건물의 수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 건물의 정보가 주어진다. 그중 $i$번째 줄에는 $i$번째로 지을 건물의 $a_i,ドル $b_i,ドル $c_i,ドル $d_i$가 공백으로 구분되어 주어진다.

출력

$N$개 줄에 걸쳐 각 울타리 공사에 드는 비용을 출력한다. 그중 $i$번째 줄에는 $i$번째로 지을 건물을 건설했을 때의 울타리 공사 비용을 출력한다.

제한

• 1ドル \le N \le 10$
• $-10 \le a_i \lt c_i \le 10$
• $-10 \le b_i \lt d_i \le 10$
• 1ドル \le i \le N$
• 주어지는 모든 좌표는 정수이다.

힌트