Problem Description

Xiao Lan is playing a new link-up game with friends. In an $n \times m$ rectangular grid, each cell contains an integer. The integer in row $i$ and column $j$ is $A_{i,j}$. The player needs to find a pair of cells $(a,b)$ and $(c,d)$ such that the integers in these two cells $A_{a,b}$ and $A_{c,d}$ are equal, and their positions satisfy $|a-c| = |b-d| > 0$. Please determine how many pairs of cells in this $n \times m$ rectangular grid satisfy the condition.

Input Format

The first line contains two positive integers $n$ and $m$, separated by a single space.

Next are $n$ lines. The $i$-th line contains $m$ positive integers $A_{i,1}, A_{i,2}, \dots, A_{i,m}$, separated by single spaces.

Output Format

Output one line containing one integer representing the answer.

3 2 
1 2 
2 3 
3 2

6

Hint

There are the following 6 pairs of cells: $(1,2)−(2,1)$, $(2,2)−(3,1)$, $(2,1)−(3,2)$, $(2,1)−(1,2)$, $(3,1)−(2,2)$, $(3,2)−(2,1)$.

Constraints

For $20\%$ of the test cases, $1 \leq n, m \leq 50$.

For all test cases, $1 \leq n, m \leq 1000$, $1 \leq A_{i,j} \leq 1000$.

Translated by ChatGPT 5