아드리아해

"천 개의 섬이 있는 땅"은 1990년대 중반 크로아티아 관광청의 공식 표어였다. 크로아티아의 섬은 1000개를 조금 넘으므로 표어가 정확하지는 않지만, 섬에서 섬으로 배를 타고 옮겨 다니는 섬 호핑이 인기 있는 여름 활동인 것은 사실이다.

이 문제에서 아드리아해의 지도는 2500행 2500열짜리 단위 정사각형 격자다. 행은 북쪽에서 남쪽으로 1번부터 2500번까지, 열은 서쪽에서 동쪽으로 1번부터 2500번까지 번호를 매긴다. 바다에는 섬이 $N$개 있고 1번부터 $N$번까지 번호가 붙어 있으며, 각 섬은 격자의 한 칸 안에 있다. $K$번 섬의 위치는 그 칸의 행 번호 $R_K$와 열 번호 $C_K$로 주어진다. 두 섬이 같은 칸에 있는 경우는 없다.

바람과 해류 때문에 한 섬에서 곧바로 갈 수 있는 섬은 그 섬의 북서쪽이나 남동쪽에 있는 섬뿐이다. 정확히 말하면 $R_A < R_B$이고 $C_A < C_B$이거나, $R_A > R_B$이고 $C_A > C_B$일 때 $A$번 섬에서 $B$번 섬으로 한 번에 건너갈 수 있다. 두 섬 사이의 거리나 그 사이에 놓인 다른 섬은 건너갈 수 있는지를 바꾸지 않는다. $A$에서 $B$로 곧바로 갈 수 없더라도 다른 섬을 거쳐 갈 수는 있다. $A$에서 $B$까지의 항해 거리는 $A$에서 $B$로 가는 데 필요한 최소 이동 횟수다.

예를 들어 아래 첫 번째 예제에서 2행 3열에 있는 섬은 네 섬으로 한 번에 건너갈 수 있고, 나머지 두 섬까지의 항해 거리는 각각 2다.

요트 대회를 준비하는 주최 측은 모든 섬을 대회 장소 후보로 검토한다. 후보 섬을 하나 정했을 때 주최 측이 알고 싶은 것은, 나머지 모든 섬이 요트를 한 척씩 보낼 때 모든 요트가 후보 섬에 도착하는 데 필요한 최소 이동 횟수의 합이다. 이 값은 나머지 모든 섬에서 후보 섬까지의 항해 거리를 모두 더한 값과 같다. 섬 $N$개의 위치가 주어질 때, 각 섬 $K$에 대해 다른 모든 섬에서 $K$번 섬까지의 항해 거리의 합을 구하는 프로그램을 작성하라.

입력으로 주어지는 어떤 두 섬 $A$, $B$에 대해서도 $A$에서 $B$로 가는 항해 경로가 존재한다.

첫째 줄에 섬의 개수 $N$ ($3 \le N \le 250\,000$)이 주어진다. 다음 $N$개 줄에 각 섬의 위치가 한 줄에 하나씩 주어진다. 각 줄에는 1 이상 2500 이하의 정수 두 개가 행 번호, 열 번호 순으로 주어진다.

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