Berland is an infinite board consisting of square fields. Rows are numbered with increasing integers from bottom to top, and columns from left to right. Let $(r, c)$ denote the field at the intersection of row $r$ and column $c$. Two different fields are called adjacent if they touch at least at a corner. This means that each field has exactly eight neighbors.

The distance between two fields $(R_A, C_A)$ and $(R_B, C_B)$ is the Euclidean distance, which is:

$$\sqrt{(R_A - R_B)^2 + (C_A - C_B)^2}$$

There are $n$ bears living in Berland. The $i$-th bear lives at field $(r_i, c_i)$. Multiple bears can be in the same field.

Bears can live alone, but everyone sometimes needs closeness. When one of the bears roars, all bears from other fields immediately move one field closer to the roaring one, moving to the adjacent field that is closest to the field with the roaring bear. It can be proven that there is always exactly one such field (there are no ties). Bears that are in the same field as the roaring one do not change their position.

For example, consider a pair of bears, one in field $(2, 1)$ and the other in field $(4, 8)$. A roar in field $(2, 1)$ will cause the second bear to move to field $(3, 7)$, which is at a distance of $\sqrt{(3 - 2)^2 + (7 - 1)^2} = \sqrt{37}$ from the source of the roar.

The bears will roar in the order $1, 2, \dots, n$, each one exactly once, except for one.

Limak has a cold. He is unable to roar and cannot leave his den, so he will remain in his initial field. Poor Limak.

You do not know which bear is Limak. For each $k$ from $1$ to $n$, find the final positions of the bears if the $k$-th one is Limak. For each possibility, output the sum of the products of the final coordinates, that is, assuming the $i$-th bear is at field $(r'_i, c'_i)$ after all $n - 1$ roars:

$$\sum_{i=1}^{n} r'_i \cdot c'_i$$

Input

The first line of input contains an integer $n$ ($2 \le n \le 250\,000$) – the number of bears. The next $n$ lines contain two integers $r_i, c_i$ ($1 \le r_i, c_i \le 10^6$) – the initial position of the $i$-th bear.

Output

Output $n$ lines. The $k$-th line should contain a single integer – the sum of the products of the final coordinates, assuming Limak is the $k$-th bear.

Examples

Input 1

4
3 5
2 1
1 4
2 1

Output 1

27
24
25
35

Note

Explanation for the example: The following figures show the situation for $k = 2$, meaning the consecutive roars are from bears $1, 3, 4$. Red circles indicate the roaring bear. The final sum of products is $2 \cdot 4 + 2 \cdot 1 + 2 \cdot 4 + 2 \cdot 3 = 24$.