F. Fitting Rectangles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer matrix $$$a$$$ with $$$m$$$ rows and $$$n$$$ columns. Both row and column indices start at $$$1$$$.

Choose two rows $$$x_1 \lt x_2$$$ and two columns $$$y_1 \lt y_2$$$ to form a subrectangle. It is a fitting rectangle if its top-left and bottom-right entries satisfy

$$$$$$a_{x_1,y_1}+a_{x_2,y_2}=(x_2-x_1)+(y_2-y_1)$$$$$$.

Count the fitting rectangles. Two rectangles are different if and only if their corresponding tuples $$$(x_1,x_2,y_1,y_2)$$$ differ.

Input

There is only one test case in each test file.

The first line contains two integers $$$m$$$ and $$$n$$$ ($$$2\le m,n\le1500$$$, $$$m\cdot n\le10^6$$$).

Each of the next $$$m$$$ lines contains $$$n$$$ integers. The $$$j$$$-th integer on the $$$i$$$-th line is $$$a_{i,j}$$$ ($$$0\le a_{i,j}\le m+n$$$).

Output

Print one integer: the number of fitting rectangles.

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

In the first example, the four fitting rectangles have top-left and bottom-right corner pairs $$$(1,3),(2,4)$$$; $$$(1,1),(3,3)$$$; $$$(1,2),(3,3)$$$; and $$$(2,1),(3,3)$$$.

In the second example, the matrix has only two rows and two columns. Since $$$x_1 \lt x_2$$$ and $$$y_1 \lt y_2$$$ must hold, the selected rows must be the first and second rows, and the selected columns must be the first and second columns. Thus there is only one subrectangle. It satisfies $$$1+1=2$$$, so the answer is $$$1$$$.