该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在二维平面上有 $N$ 个点 $P_1, P_2, \dots, P_N$，每个点 $P_i$ 的坐标为 $(X_i, Y_i)$。
定义两个点 $A$ 和 $B$ 之间的距离 $\text{dist}(A, B)$ 为：

假设兔子最初位于点 $A$。
兔子可以在 $(x, y)$ 处跳跃到 $(x+1, y+1)$、$(x+1, y-1)$、$(x-1, y+1)$ 或 $(x-1, y-1)$ 中的任意一个位置。
从点 $A$ 跳跃到点 $B$ 所需的最小跳跃次数就是 $\text{dist}(A, B)$。
如果无法通过跳跃从点 $A$ 到达点 $B$，则 $\text{dist}(A, B) = 0$。

要求计算以下表达式的值：

$$\sum_{i=1}^{N-1} \sum_{j=i+1}^N \text{dist}(P_i, P_j)$$

输入格式

输入的第一行包含一个整数 $N$，表示点的个数。

接下来的 $N$ 行，每行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个点 $P_i$ 的坐标。

输出格式

输出一个整数，表示 $\sum_{i=1}^{N-1} \sum_{j=i+1}^N \text{dist}(P_i, P_j)$ 的值。

输入输出样例

3
0 0
1 3
5 6

3

5
0 5
1 7
2 9
3 8
4 6

11

说明/提示

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq X_i, Y_i \leq 10^8$
• 对于任意 $i \neq j$，点 $(X_i, Y_i)$ 和 $(X_j, Y_j)$ 不相同
• 输入数据中的所有整数均为非负整数

样例解释 1

对于输入中的点 $P_1, P_2, P_3$，它们的坐标分别为 $(0, 0)$，$(1, 3)$ 和 $(5, 6)$。

• 从 $P_1$ 到 $P_2$，兔子需要跳跃 3 次才能到达，因此 $\text{dist}(P_1, P_2) = 3$。
• 从 $P_1$ 到 $P_3$，以及从 $P_2$ 到 $P_3$，兔子无法到达，因此 $\text{dist}(P_1, P_3) = \text{dist}(P_2, P_3) = 0$。

因此，答案为：

$$\text{dist}(P_1, P_2) + \text{dist}(P_1, P_3) + \text{dist}(P_2, P_3) = 3 + 0 + 0 = 3$$

样例解释 2

对于输入中的点 $P_1, P_2, P_3, P_4, P_5$，它们的坐标分别为 $(0, 5)$，$(1, 7)$，$(2, 9)$，$(3, 8)$ 和 $(4, 6)$。
通过类似的计算方法，得到结果：

$$\sum_{i=1}^{4} \sum_{j=i+1}^5 \text{dist}(P_i, P_j) = 11$$