Strange sum

문제

Egor has table of size $n\times mn\; \backslash times\; m$, where all lines are numbered from $11$ to $nn$ and all columns are numbered from $11$ to $mm$. Each cell is painted in some color that can be presented as integer from $11$ to ${10}^{9}10^9$.

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

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

입력

The first line contains two integers $nn$ and $mm$ ($1\le n\le m1\; \backslash leq\; n\; \backslash le\; m$, $n\cdot m\le 500000n\; \backslash cdot\; m\; \backslash leq\; 500\backslash ,000$) --- number of rows and columns in the table.

Each of next $nn$ lines describes the rows of the table. $ii$-th line contains $mm$ integers $c_{i1},c_{i2},\dots ,c_{im}c\_\{i1\},\; c\_\{i2\},\; \backslash ldots,\; c\_\{im\}$ ($1\le c_{ij}\le {10}^{9}1\; \backslash le\; c\_\{ij\}\; \backslash le\; 10^9$) --- colors of cells in $ii$-th row.

출력

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

힌트

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

2 3
1 2 3
3 2 1

7

3 4
1 1 2 2
2 1 1 2
2 2 1 1

76

4 4
1 1 2 3
2 1 1 2
3 1 2 1
1 1 2 1

129