题目描述

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

Let us call the cell that lies in $r$-th row and $c$-th column as $(r, c)$. We define the $\emph{manhattan distance}$ between two cells $(r_1, c_1)$ and $(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)$ 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 same color. Help him to calculate this sum.

输入格式

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

Each of next $n$ lines describes the rows of the table. $i$-th line contains $m$ integers $c_{i1}, c_{i2}, \ldots, c_{im}$ ($1 \le c_{ij} \le 10^9$) --- colors of cells in $i$-th row.

输出格式

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

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

提示

Note

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

Scoring

Tests for this problem are divided into 5 groups. For each of the groups you earn points only if your solution passes all tests in this group and all tests in some of the previous groups. Note that your solution may not pass the sample tests, but it will still be accepted for evaluation

We define $C$ as the maximum number of color in the table.

Group	Points	Additional constraints	<		Required groups	Comment
		$n$	$n \cdot m$	$C$
0	$0$	--	--	--		Sample tests
1	$23$		$n \cdot m \le 1000$		$0$
2	$17$	$n=1$	--
3	$15$	$n=2$
4	$20$	--		$C \le 2$
5	$25$			--	$0$--$4$