Returning to Farming

Time limit1sMemory limit256 MB

Summary

Count unordered pairs of non-empty axis-aligned rectangles on an N x N grid that touch at exactly one corner and have equal total cell profit.

Level: Hard8 of 10
Topics: Prefix sum, Hash map, Geometry, Combinatorics
Solved: No attempts yet

Problem

Two people are moving from the city to a friend's square farm. The farm has size N x N and is divided into 1 x 1 cells. The profit of cell (i, j) is Aij, and this value may be negative.

The friend will lend each person one non-empty rectangular part of the farm. Each rectangle must have sides parallel to the grid lines.

The friend wants the two rectangles to have the same total profit. To encourage competition without letting the two areas share an edge, the two rectangles must meet at exactly one corner point. They must not overlap or share an edge segment.

Count the number of unordered ways to choose the two rectangles. Swapping the two people does not make a new way.

Input

The first line contains the size of the farm, N (1 <= N <= 50).

Each of the next N lines contains N integers. The j-th integer on the i-th line is Aij, the profit of cell (i, j) (-1000 < Aij < 1000).

Output

Print the number of ways to lend two rectangles satisfying the conditions.

Hint

For the first visible test, the possible pairs are as follows, using zero-based cell coordinates and inclusive rectangle endpoints.

(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)

Examples3

Example 1
Input
```
3
1 2 3
2 3 4
3 4 8
```
Expected output
```
7
```

Example 2

Input

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

Expected output

Example 3

Input

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

Expected output