Strange sum

Interview

Time limit3sMemory limit1024 MB

Summary

Given a grid of colored cells, compute the sum of Manhattan distances over all pairs of cells that share a color.

Level: Medium5 of 10
Topics: Hash map, Sorting, Prefix sum
Solved: No attempts yet

Statement

Egor has a table with $n$ rows and $m$ columns. Rows are numbered 1 to $n$ , and columns are numbered 1 to $m$ . Each cell is painted with a color, an integer from 1 to $10^9$ .

The cell in row $r$ and column $c$ is written $(r, c)$ . The manhattan distance between cells $(r_1, c_1)$ and $(r_2, c_2)$ is the length of the shortest path between them, where consecutive cells share a side. The path may pass through cells of any color. For example, the distance between $(1, 2)$ and $(3, 3)$ is 3, and one shortest path is $(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$ .

Egor wants the sum of manhattan distances over every pair of cells that have the same color. Compute this sum.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq m$ , $n \cdot m \leq 500000$ ), the number of rows and columns.

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

Output

Print one integer, the sum of manhattan distances over all pairs of cells with the same color.

Hint

In the first sample, there are three pairs of cells with the same color: $(1, 1)$ and $(2, 3)$ , $(1, 2)$ and $(2, 2)$ , and $(1, 3)$ and $(2, 1)$ . Their manhattan distances are 3, 1, and 3, so the sum is 7.

Examples3

Example 1
Input
```
2 3
1 2 3
3 2 1
```
Expected output
```
7
```
Example 2
Input
```
3 4
1 1 2 2
2 1 1 2
2 2 1 1
```
Expected output
```
76
```

Example 3

Input

Expected output