Pattern Recognition

Pattern Recognition

Time limit: 1 s.
Memory limit: 256 MB

You just bought a desert! The desert is divided into \(n\) rows and \(m\) columns. In the cell at row \(i\) and column \(j\), there is a camel of type \(A_{i,j}\). There are \(k\) camel types in total, so each \(A_{i,j}\) is an integer between \(1\) and \(k\).

You are interested in special regions of the desert. A region is considered special if:

  • it is rectangular,
  • all camels inside it are of the same type, and
  • that camel type appears only inside that rectangle and nowhere else.

Your task is to determine how many special regions the desert contains.

Input

The first line of input contains three integers \(n\), \(m\) and \(k\) (\(1 \leq n, m \leq 2000\) and \(1 \leq k \leq 10^6\)) - the number of rows of the desert, the number of columns of the desert, and the number of camel types.

Each of the next n lines contains n integers separated by spaces. The \(j\)-th number in the \(i\)-th line represents \(A_{i,j}\), the type of camel in row \(i\), column \(j\).

Output

Output a single integer - the number of special regions in the desert.

Scoring

Subtask Additional constraints Points
\(1\) \(n, m \le 20\) \(14\)
\(2\) \(n, m \le 100, k \le 100\) \(16\)
\(3\) \(n, m \le 100\) \(17\)
\(4\) \(k = 2\) \(22\)
\(5\) no additional constraints \(31\)

Examples

Input

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

Output

1

Input

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

Output

4

Note

Fast input: To pass the full constraints, you may need to use fast input/output. In C++, add the following lines at the beginning of the main function:

ios::sync_with_stdio(false);
cin.tie(nullptr);

Samples Explanations:

In the first sample, type 1 forms a perfect 2 times 2 rectangle and does not appear anywhere else, so valid. Type 2 has a bounding box of size 2 times 2, but one cell inside is not 2, so invalid. Type 3 appears in multiple rows and its bounding box contains cells that are not 3, so invalid. So, there is exactly 1 special region.

In the second example, each type (1, 2, 3, 4) forms exactly one full rectangle and appears nowhere else. All of them satisfy the conditions. So, the answer is 4.

Solution

For each camel type, find its minimum and maximum row and column. These four values define the only rectangle that could contain all occurrences of that type.

Also count its occurrences. The type fills its bounding rectangle exactly when

\[ \text{count}=(\text{maxRow}-\text{minRow}+1) (\text{maxCol}-\text{minCol}+1). \]

If the equality holds, every cell of the rectangle has that type, so it forms one special region.

The complexity is \(O(NM+K)\) time and \(O(K)\) memory.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);

        int n, m, k;
        cin >> n >> m >> k;

        vector<int> minRow(k + 1, n), maxRow(k + 1, -1);
        vector<int> minCol(k + 1, m), maxCol(k + 1, -1);
        vector<int> count(k + 1, 0);

        for (int row = 0; row < n; row++) {
                for (int col = 0; col < m; col++) {
                        int type;
                        cin >> type;
                        minRow[type] = min(minRow[type], row);
                        maxRow[type] = max(maxRow[type], row);
                        minCol[type] = min(minCol[type], col);
                        maxCol[type] = max(maxCol[type], col);
                        count[type]++;
                }
        }

        int answer = 0;

        for (int type = 1; type <= k; type++) {
                if (count[type] == 0) continue;

                long long area = 1LL * (maxRow[type] - minRow[type] + 1)
                                                            * (maxCol[type] - minCol[type] + 1);
                if (area == count[type]) {
                        answer++;
                }
        }

        cout << answer << '\n';
}