Description

Person A has an $n \times m$ grid. Some cells are white, and the remaining cells are black.

Person A chooses four integers $x_1, x_2, y_1, y_2$ satisfying the following conditions:

1. $1 \le x_1 < x_2 \le n$ and $1 \le y_1 < y_2 \le m$.
2. $x_1 + x_2$ is even.

If all cells on the following three segments are white: $(x_1,y_1)\to(x_2,y_1)$, $(x_1,y_2)\to(x_2,y_2)$, $(\frac{x_1+x_2}{2},y_1)\to(\frac{x_1+x_2}{2},y_2)$, then the shape formed by these three segments is called an H-shape.

Person A wants to know how many different H-shapes exist in the grid.

Two H-shapes are the same if and only if their $x_1, x_2, y_1, y_2$ are all the same.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain $m$ integers describing the grid, where $0$ means a white cell and $1$ means a black cell.

Output Format

Output one integer, representing the number of different H-shapes.

3 4
1 0 0 0
1 1 0 0
1 0 0 0

1

5 3
0 1 0
0 1 0
0 0 0
0 1 0
0 1 0

2

Hint

[Sample 1 Explanation]

The H-shape with $(x_1,x_2,y_1,y_2)=(1,3,3,4)$ is valid.

[Sample 2 Explanation]

The H-shapes with $(x_1,x_2,y_1,y_2)=(1,5,1,3)$ and $(2,4,1,3)$ are valid.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (1 point): $n=2$.
• Subtask 2 (9 points): $n, m \le 50$.
• Subtask 3 (10 points): $n, m \le 100$, time limit is $500ms$.
• Subtask 4 (30 points): $n, m \le 500$.
• Subtask 5 (50 points): no special constraints.

For $100\%$ of the data, $2 \le n, m \le 2 \times 10^3$.

Translated by ChatGPT 5