Bear Roar Simulation

Berlandia is an infinite grid of unit square cells. The rows are numbered with increasing integers from bottom to top and the columns with increasing integers from left to right. A cell is denoted by (r, c) representing the cell in row r and column c.

Two distinct cells are adjacent if they share at least one vertex (i.e. they are 8-connected). The Euclidean distance between two cells (R_A, C_A) and (R_B, C_B) is given by $$ \sqrt{(R_A-R_B)^2+(C_A-C_B)^2} $$

There are n bears living in Berlandia. The i-th bear lives in cell (r_i,c_i). Several bears may initially occupy the same cell.

Bears normally can live on their own, but sometimes they get close to one another. When a bear roars, every bear in a different cell immediately moves to the unique adjacent cell (one of the 8 neighbors) that minimizes its Euclidean distance to the roaring bear’s cell. (Bears which are in the same cell as the roaring bear do not move.)

The bears will roar one by one in the order from 1 to n. However, one bear, named Limak, is too cold to roar and he also cannot leave his cell. Unfortunately, you do not know which bear is Limak. For each k from 1 to n, assume that the k-th bear is Limak. Simulate the process and determine the final positions of the bears. Let the final position of the i-th bear be (r_i', c_i') after the n-1 roars. For that scenario, output the value:

You are to compute this sum for every possible candidate of Limak.

inputFormat

The first line contains a single integer n (number of bears). Each of the next n lines contains two integers r_i and c_i representing the initial row and column of the i-th bear.

outputFormat

Output n lines. The k-th line should contain the sum \(\sum_{i=1}^n r_i' c_i'\) after simulating the process when the k-th bear is assumed to be Limak.

sample

2
2 1
4 8

34
34