CF1648A.Weird Sum

Egor has a table of size $n \times m$, with lines numbered from $1$ to $n$ and columns numbered from $1$ to $m$. Each cell has a color that can be presented as an integer from $1$ to $10^5$.

Let us denote the cell that lies in the intersection of the $r$-th row and the $c$-th column as $(r, c)$. We define the manhattan distance between two cells $(r_1, c_1)$ and $(r_2, c_2)$ as the length of a shortest path between them where each consecutive cells in the path must have a common side. The path can go through cells of any color. For example, in the table $3 \times 4$ the manhattan distance between $(1, 2)$ and $(3, 3)$ is $3$, one of the shortest paths is the following: $(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$.

Egor decided to calculate the sum of manhattan distances between each pair of cells of the same color. Help him to calculate this sum.

叶戈尔有一个 $n \times m$ 的表格，行编号为 $1$ 到 $n$，列编号为 $1$ 到 $m$。每个单元格有一种颜色，可用 $1$ 到 $10^5$ 之间的整数表示。

我们将位于第 $r$ 行、第 $c$ 列的单元格记作 $(r, c)$。我们定义两个单元格 $(r_1, c_1)$ 和 $(r_2, c_2)$ 之间的曼哈顿距离为它们之间最短路径的长度，其中该路径上任意两个相邻单元格必须共享一条边（即上下左右相邻）。路径可以经过任意颜色的单元格。例如，在一个 $3 \times 4$ 的表格中，$(1, 2)$ 与 $(3, 3)$ 之间的曼哈顿距离为 $3$，其中一条最短路径如下：$(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$。

叶戈尔决定计算所有颜色相同的单元格对之间的曼哈顿距离之和。请帮助他计算该总和。

The first line contains two integers $n$ and $m$ ($1 \leq n \le m$, $n \cdot m \leq 100\,000$) — number of rows and columns in the table.

Each of next $n$ lines describes a row of the table. The $i$-th line contains $m$ integers $c_{i1}, c_{i2}, \ldots, c_{im}$ ($1 \le c_{ij} \le 100\,000$) — colors of cells in the $i$-th row.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \le m$，且 $n \cdot m \leq 100\,000$），分别表示表格的行数和列数。

接下来的 $n$ 行每行描述表格的一行。第 $i$ 行包含 $m$ 个整数 $c_{i1}, c_{i2}, \ldots, c_{im}$（$1 \le c_{ij} \le 100\,000$），表示第 $i$ 行各单元格的颜色。

Print one integer — the the sum of manhattan distances between each pair of cells of the same color.

输出一个整数——所有同色单元格对之间的曼哈顿距离之和。

In the first sample there are three pairs of cells of same color: in cells $(1, 1)$ and $(2, 3)$, in cells $(1, 2)$ and $(2, 2)$, in cells $(1, 3)$ and $(2, 1)$. The manhattan distances between them are $3$, $1$ and $3$, the sum is $7$.

在第一个样例中，有三对同色的格子：$(1, 1)$ 和 $(2, 3)$、$(1, 2)$ 和 $(2, 2)$、$(1, 3)$ 和 $(2, 1)$。它们之间的曼哈顿距离分别为 $3$、$1$ 和 $3$，总和为 $7$。