섬 항해 Batch 컴파일 명령

크로아티아는 섬들이 엄청 많기로 유명해서, 여름이면 섬들 사이를 항해하는 활동을 하기도 합니다. 여기로 관광을 갈 계획인 승현이는 놀 생각은 안 하고 이런 문제를 생각해 내게 됩니다.

크로아티아가 있는 아드리아 해의 지도는 편의상 2500개의 행과 2500개의 열로 구성된 격자판이라고 생각해 보겠습니다. 행 번호는 위에서 아래로 1부터 2500까지, 열 번호는 왼쪽에서 오른쪽으로 1부터 2500까지 붙어 있습니다. 바다에는 1부터 $N$까지의 번호가 붙은 $N$개의 섬이 있고, 각 섬은 격자 하나 안에 들어 있습니다. $K$번째 섬의 위치는 행 번호 $R_{K}$와 열 번호 $C_{K}$를 통해 주어집니다. 어떠한 두 섬도 같은 격자 안에 있지 않다는 것은 보장됩니다.

[그림 1] 아래 입력 예제를 나타낸 그림

기후 상태를 보아, 북서쪽 또는 남동쪽으로만 똑바로 항해를 할 수 있다고 합니다. 다시 말해, $A$번 섬에서 $B$번 섬으로 한 번에 이동하려면 $R_{A} < R_{B}, C_{A} < C_{B}$(둘 다 만족) 또는 $R_{A} > R_{B}, C_{A} > C_{B}$(둘 다 만족)여야 합니다. 두 섬 간의 거리나 사이에 있는 섬들은 항해 가능 여부에 아무 영향도 미치지 않습니다. $A$번 섬에서 $B$번 섬으로 곧장 항해할 수 없다면, 다른 섬들을 몇 번 거쳐서 이동이 가능할 수도 있습니다. $A$번 섬과 $B$번 섬 사이의 항해 거리는 $A$번 섬에서 $B$번 섬으로 가기 위해 거쳐야 할 섬들의 수 ($A$번 섬 제외)로 정의됩니다.

예로 들어, [그림 1]에서 2행 3열의 섬에서 출발한다면, 4개의 섬과의 항해 거리는 1, 2개의 섬과는 항해 거리가 2가 됩니다.

해야 할 일

승현이는 관광을 위해 $N$개의 섬에서 가이드를 한 명씩 섭외했고, 이들은 어느 한 섬에 모여 있기로 했습니다. 가이드들은 자신의 섬에서 배를 타고 항해해서 모입니다. (위 조건을 만족하도록 항해해야겠죠) 비용을 아끼기 위해서, 그들은 각 후보 섬들에 대해 다른 모든 섬들과 이 후보 섬 사이의 항해 거리들의 합을 알고자 합니다. $N$개 섬들의 위치가 주어질 때, 모든 섬들에 대해 이 값을 계산하는 프로그램을 작성하세요.

테스트 데이터는 임의의 두 섬 $A$에서 $B$로 항해하여 이동할 수 있도록 만들어졌습니다. 그러니까 도달 불가능한 경우는 없습니다.

입력 형식

첫 번째 줄에 섬의 수 $N$ ($3 \le N \le 250,000$)이 주어집니다. 다음 $N$개 줄에 섬들의 위치가 주어집니다. 각 위치는 섬의 행 번호와 열 번호로 주어집니다.

출력 형식

$N$개의 줄을 출력합니다. 입력에서 주어진 순서대로, 각 섬에 대해, 다른 모든 섬들과의 항해 거리들의 합을 한 줄에 하나씩 출력하면 됩니다.

채점 방식

• 25%에 해당하는 테스트 데이터에 대해 $N$은 최대 10.
• 50%에 해당하는 테스트 데이터에 대해 $N$은 최대 1500.
• 60%에 해당하는 테스트 데이터에 대해 $N$은 최대 5000.
• 80%에 해당하는 테스트 데이터에 대해 $N$은 최대 25000.

입출력 예제