E. Matrix Distances
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Ham has a matrix of size $$$ n \times m $$$, where each cell is filled with a color value $$$c_{i,j}$$$. Mr. Ham is interested in the relationships between cells of the same color and wants to calculate the sum of Manhattan distances between all pairs of cells with the same color.

The Manhattan distance between two cells $$$ (x_1, y_1) $$$ and $$$ (x_2, y_2) $$$ is given by $$$ d_M = \left|x_1 - x_2\right| + \left|y_1 - y_2\right| $$$.

Formally, please compute:

$$$$$$\text{Total Sum} = \sum_C \sum_{(x_i, y_i) \in S_C} \sum_{(x_j, y_j)\in S_C} \left|x_i-x_j\right|+\left|y_i-y_j\right|$$$$$$

Here, $$$C$$$ denotes the set of all distinct colors. $$$ S_C $$$ denotes the set of coordinates $$$ (x, y) $$$ with the color value equal to the specified color $$$C$$$.

Input

The first line contains two integers $$$ n $$$ and $$$ m $$$ (1$$$\leq n, m \leq 1000$$$), representing the number of rows and columns in the matrix.

The following contains n lines. Each line $$$i$$$ contains $$$m$$$ space-separated integers $$$c_{i,j}$$$ ($$$1 \leq c_{i,j} \leq 10^9$$$), representing the color values in the matrix.

Output

Output a single integer, the sum of Manhattan distances for all pairs of cells with the same color.

Examples
Input
2 2
1 1
2 2
Output
4
Input
4 4
1 3 2 4
2 1 2 3
1 3 3 2
3 2 1 4
Output
152
Note

In the first example, the distinct color values are $$$1$$$ and $$$2$$$.

  1. For color $$$1$$$:
    • The coordinates with color $$$1$$$ are $$$(1, 1)$$$ and $$$(1, 2)$$$.
    • The Manhattan distance between $$$(1, 1)$$$ and $$$(1, 1)$$$ is $$$|1-1| + |1-1| = 0$$$.
    • The Manhattan distance between $$$(1, 1)$$$ and $$$(1, 2)$$$ is $$$|1-1| + |1-2| = 1$$$.
    • The Manhattan distance between $$$(1, 2)$$$ and $$$(1, 1)$$$ is $$$|1-1| + |2-1| = 1$$$.
    • The Manhattan distance between $$$(1, 2)$$$ and $$$(1, 2)$$$ is $$$|1-1| + |2-2| = 0$$$.
  2. For color $$$2$$$:
    • The coordinates with color $$$1$$$ are $$$(2, 1)$$$ and $$$(2, 2)$$$.
    • The Manhattan distance between $$$(2, 1)$$$ and $$$(2, 1)$$$ is $$$|2-2| + |1-1| = 0$$$.
    • The Manhattan distance between $$$(2, 1)$$$ and $$$(2, 2)$$$ is $$$|2-2| + |1-2| = 1$$$.
    • The Manhattan distance between $$$(2, 2)$$$ and $$$(2, 1)$$$ is $$$|2-2| + |2-1| = 1$$$.
    • The Manhattan distance between $$$(2, 2)$$$ and $$$(2, 2)$$$ is $$$|2-2| + |2-2| = 0$$$.
So, the total sum of Manhattan distances for all pairs of cells with the same color is $$$1+1+1+1=4$$$.