Hide

Bob

Little Bob is a famous builder. He bought land and wants to build a house. Unfortunately, the problem is the land’s terrain, it has a variable elevation.

The land is shaped like a rectangle, $N$ meters wide and $M$ meters long. It can be divided into $N\cdot M$ squares (see the image). Bob’s house will be shaped like a rectangle that has sides parallel with the land’s edges and its vertices coincide with the vertices of the squares. All the land covered by Bob’s house must be of equal elevation to prevent it from collapsing.

\includegraphics{img1.pdf}
Figure 1: The land divided into squares. Two possible locations of the house are marked with red and blue.

Calculate the number of ways Bob can build his house!

Input

The first line of input contains integers $N$ and $M$ ($1 \leq N, M \leq 1\, 000$).

Each of the following $N$ lines contains $M$ integers $a_{ij}$ ($1 \leq a_{ij} \leq 10^9$), respectively the height of each square of land.

Warning: Please use faster input methods beacuse the amount of input is very large. For example, either set ios::sync_with_stdio(false) or use scanf instead of cin in C++, and use BufferedReader instead of Scanner in Java.

Output

The first and only line of output must contain the required number from the task statement.

Sample Input 1 Sample Output 1
5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1
27
Sample Input 2 Sample Output 2
4 3
1 1 1
1 1 1
2 2 2
2 2 2
36
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in