Berlandia 是一个由正方形格子组成的无限棋盘。行从下到上用递增的整数编号，列从左到右编号。令 $(r, c)$ 表示第 $r$ 行第 $c$ 列的格子。如果两个不同的格子至少有一个公共角，则称它们相邻。这意味着每个格子恰好有八个邻居。

两个格子 $(R_A, C_A)$ 和 $(R_B, C_B)$ 之间的距离为欧几里得距离，即： $$\sqrt{(R_A - R_B)^2 + (C_A - C_B)^2}$$

Berlandia 生活着 $n$ 只熊。第 $i$ 只熊居住在格子 $(r_i, c_i)$。一个格子中可能有多只熊。

熊可以独自生活，但有时需要亲近感。当其中一只熊吼叫时，所有其他格子上的熊会立即向吼叫的熊靠近一格，移动到相邻格子中距离吼叫者最近的那一个。可以证明，这样的格子总是唯一的（不存在平局）。与吼叫者处于同一格子的熊不会改变位置。

例如，考虑一对熊，一只在 $(2, 1)$，另一只在 $(4, 8)$。在 $(2, 1)$ 处的吼叫会使第二只熊移动到 $(3, 7)$，该位置距离吼叫源的距离为 $\sqrt{(3 - 2)^2 + (7 - 1)^2} = \sqrt{37}$。

熊会按 $1, 2, \dots, n$ 的顺序依次吼叫，每只熊吼叫一次，但有一只除外。 Limak 感冒了。他无法吼叫，也不能离开他的巢穴，因此他将保持在初始位置。可怜的 Limak。

你不知道哪只是 Limak。对于每个 $k$ 从 $1$ 到 $n$，如果第 $k$ 只熊是 Limak，请找出所有熊的最终位置。对于每种可能性，输出最终坐标乘积之和，即假设第 $i$ 只熊在所有 $n-1$ 次吼叫后的位置为 $(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$ 只熊的初始位置。

输出格式

输出 $n$ 行。第 $k$ 行应包含一个整数，表示假设 Limak 是第 $k$ 只熊时的最终坐标乘积之和。

样例

样例输入 1

4
3 5
2 1
1 4
2 1

样例输出 1

27
24
25
35

说明 1

样例说明：下图展示了 $k = 2$ 时的情形，即吼叫顺序为 1, 3, 4。红色圆圈表示正在吼叫的熊。最终乘积之和为 $2 \cdot 4 + 2 \cdot 1 + 2 \cdot 4 + 2 \cdot 3 = 24$。

子任务

在某些测试组中，$c_i = 1$ 对所有 $i$ 成立。 我们保证在每个测试中至少满足以下三个条件之一： $n \le 10^5$ $c_i = 1$ 对所有 $i$ 成立 * 时间限制恰好为 8 秒