Problem Description

This problem is translated from PA 2018 Round 5 Ryki.

Berlandia is an infinite chessboard made of square cells. Rows are numbered with increasing integers from bottom to top, and columns are numbered with increasing integers from left to right. Let $(r,c)$ denote the cell in row $r$ and column $c$. If two different cells share at least one corner, we call them adjacent. This means the cells are 8-connected.

The distance between two cells $(R_A,C_A)$ and $(R_B,C_B)$ is the Euclidean distance, i.e.:

There are $n$ bears living in Berlandia. The $i$-th bear lives in cell $(r_i,c_i)$. Multiple bears may live in the same cell.

Bears can live alone, but sometimes they move closer to each other. When a bear roars, all bears in other cells immediately move to the adjacent cell that is closest to the roaring bear. It can be proven that there is exactly one such cell (no ties occur). Bears in the same cell as the roaring bear do not move.

For example, consider two bears: one in cell $(2,1)$ and the other in cell $(4,8)$. If the bear in $(2,1)$ roars, the other bear will move to cell $(3,7)$, and their final distance becomes $\sqrt{(3-2)^2+(7-1)^2}=\sqrt{37}$.

The bears will roar one by one in the order: first bear, second bear, ..., last bear. Except for one bear called Limak: he is too cold to roar, and he also cannot leave his cell. Poor Limak.

However, you do not know which bear is Limak. For each $k$ from $1$ to $n$, assuming the $k$-th bear is Limak, find the final positions of all bears. For each possibility, it is enough to output the sum of the products of the row and column coordinates of all bears. That is, suppose that after $n-1$ roars, the $i$-th bear is at $(r_i',c_i')$, output:

Input Format

The first line contains a positive integer $n\ (2\le n\le 250\ 000)$, the number of bears.

The next $n$ lines each contain two integers $r_i,c_i\ (1\le r_i,c_i\le 10^6)$. The $i$-th of these lines gives the initial position of the $i$-th bear.

Output Format

Output $n$ lines. In the $k$-th line, output one integer: assuming Limak is the $k$-th bear, the sum of the products of row and column coordinates of all bears after the process ends.

4
3 5
2 1
1 4
2 1

27
24
25
35

Hint

Explanation for Sample 1

The figure below shows the case $k=2$, i.e. the roaring order is $1,3,4$. The red circles indicate the roaring bears. The final sum of products is $2 \cdot 4 + 2 \cdot 1 + 2 \cdot 4 + 2 \cdot 3 = 24$.

Constraints

This problem uses bundled testdata.

It is guaranteed that in each subtask, at least one of the following three cases occurs:

• $n\le 10^5$
• For all $i$, $c_i=1$
• The time limit is $8$ seconds

Note: Since the detailed time limits for each test point were not published, the time limit for all test points of this problem is $4$ seconds.

Translated by ChatGPT 5