Ryki

베를란디아는 정사각형 칸으로 이루어진 끝없는 판이다. 행은 아래에서 위로 갈수록 커지는 정수로 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 번호가 매겨진다. $(r, c)$는 $r$행과 $c$열이 만나는 칸을 뜻한다. 서로 다른 두 칸은 적어도 꼭짓점이 맞닿으면 인접한다고 본다. 따라서 모든 칸은 인접한 칸이 정확히 8개다.

칸 $(R_A, C_A)$와 $(R_B, C_B)$ 사이의 거리는 유클리드 거리이다. $\sqrt{(R_A - R_B)^2 + (C_A - C_B)^2}$

베를란디아에는 $n$마리의 곰이 산다. $i$번 곰은 $(r_i, c_i)$ 칸에 산다. 한 칸에 여러 마리의 곰이 있을 수 있다.

곰은 혼자 지내기도 하지만 가끔은 가까이 있는 동료가 필요하다. 곰 한 마리가 포효하면, 다른 칸에 있는 모든 곰이 즉시 포효한 곰 쪽으로 한 칸씩 다가간다. 각 곰은 인접한 칸 중에서 포효한 곰의 칸과 가장 가까운 칸으로 이동한다. 그런 칸은 항상 하나뿐이며 동점은 없다. 포효한 곰과 같은 칸에 있는 곰은 움직이지 않는다.

예를 들어 $(2, 1)$ 칸에 곰 한 마리가, $(4, 8)$ 칸에 다른 곰 한 마리가 있다고 하자. 첫 번째 곰이 포효하면 두 번째 곰은 $(3, 7)$ 칸으로 이동한다. 이 칸은 포효한 위치에서 $\sqrt{(3 - 2)^2 + (7 - 1)^2} = \sqrt{37}$만큼 떨어져 있다.

곰들은 $1, 2, \dots, n$ 순서로 한 번씩 포효한다. 단, 한 마리는 포효하지 않는다.

Limak은 감기에 걸렸다. Limak은 포효할 수 없고 굴 밖으로 나갈 수도 없으므로 처음 칸에 그대로 머문다. 불쌍한 Limak.

어떤 곰이 Limak인지는 알 수 없다. $k$를 $1$부터 $n$까지 바꿔 가며, $k$번 곰이 Limak인 경우의 곰들의 최종 위치를 구하라. 각 경우마다 최종 좌표의 곱을 모두 더한 값을 구한다. $n-1$번의 포효 후 $i$번 곰이 $(r'_i, c'_i)$ 칸에 있다면, 다음 값을 구한다. $\sum_{i=1}^{n} r'_i \cdot c'_i$

첫 줄에 곰의 수 $n$ ($2 \le n \le 250\,000$)이 주어진다.

이어지는 $n$개의 줄에는 정수 $r_i$와 $c_i$ ($1 \le r_i, c_i \le 10^6$)가 주어진다. $i$번째 줄은 $i$번 곰의 처음 위치이다.

$n$개의 줄을 출력한다. $k$번째 줄에는 $k$번 곰이 Limak일 때 최종 좌표 곱의 합을 정수 하나로 출력한다.