Problem Description

Given an $n \times n$ matrix, determine how many pairs of submatrices have exactly one common vertex and have equal element sums.

Note that the common vertex here means that the two submatrices touch at a corner, not that they share a common cell. Please refer to Sample 1 to understand the meaning of a common vertex.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain $n$ integers, denoted as $a_{i,j}$, and they may be negative.

Output Format

Output a single line containing the number of valid pairs.

3
1 2 3
2 3 4
3 4 8

7

4
-1 -1 -1 -1
1 2 3 4
1 2 3 4
1 2 3 4

10

5
-1 -1 -1 -1 -1
-2 -2 -2 -2 -2
-3 -3 -3 -3 -3
-4 -4 -4 -4 -4
-5 -5 -5 -5 -5

36

Hint

Constraints

• For $40\%$ of the testdata, $1 \le n \le 10$.
• For $100\%$ of the testdata, $1 \le n \le 50$, $-1000 \le a_{i,j} \le 1000$.

Sample 1 Explanation

The possible rectangle pairs are:

$(0,0)-(1,1)$ and $(2,2)-(2,2)$;

$(1,0)-(1,0)$ and $(0,1)-(0,1)$;

$(2,0)-(2,0)$ and $(1,1)-(1,1)$;

$(1,1)-(1,1)$ and $(0,2)-(0,2)$;

$(2,1)-(2,1)$ and $(1,2)-(1,2)$;

$(2,0)-(2,1)$ and $(0,2)-(1,2)$;

$(1,0)-(2,0)$ and $(0,1)-(0,2)$.

In total there are $7$ pairs, so the output is $7$.

Note

Translated from COCI2013-2014 CONTEST #1 T3 RATAR.

$\mathtt{Subtask \ 0}$ is the sample testdata. (10 pts)

In $\mathtt{Subtask \ 1}$, all testdata satisfy $1 \le n \le 10$. (30 pts)

In $\mathtt{Subtask \ 2}$, all testdata satisfy $1 \le n \le 50$, $-1000 \le a_{i,j} \le 1000$. Please note the time limit for this subtask. (60 pts)

Translated by ChatGPT 5