409875: GYM103821 G Angry Bsher

Coach Ali Zibak was the chief judge of the first local contest, the problem set was very hard and this made coach Bsher very angry so he decided to put this hard problem.

Given $$$N \times M$$$ grid, each cell contains a digit written on it. Two cells are connected if they share a side and have the same digit written on them. Connected cells form a connected component. You have to process two types of queries:

• $$$1$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$.
• $$$2$$$ $$$x$$$ $$$y$$$.

In the first query you are given a sub-grid in the grid, the sub-grid is defined by two points, the first point is the upper left corner with indices $$$x_1$$$ $$$y_1$$$, the second point is the lower right corner with indices $$$x_2$$$ $$$y_2$$$, and you have to count the number of fully and partially contained components in this sub-grid.

A component is said to be fully contained if all its cells are in the given sub-grid, if at least one cell is inside the sub-grid, and at least one cell is outside it. This component is said to be partially contained.

In the second query you put a wall at cell $$$x, y$$$. Blocking it and removing any connected cells to it.

The first line contains a single integer $$$T$$$ ($$$1\le T \le 10^4$$$) — Number of test cases to process.

The first line of each test case contains three integers $$$N$$$, $$$M$$$ and $$$Q$$$ ($$$1 \le N, M \le 500$$$), ($$$1 \le Q \le 10^4$$$) — Width and Height of the grid, and number of queries to process.

Each of the next $$$N$$$ lines contains $$$M$$$ numbers, description of the grid ($$$1\le grid_{i, j} \le 9$$$).

Next $$$Q$$$ lines contain the description of each query, as described in the problem statement.

It's guaranteed that sum of $$$N \times M$$$ over all test cases is at most $$$250\,000$$$ and sum of $$$Q$$$ over all test cases is at most $$$10^4$$$.

For each query of the first type print two numbers, number of fully and partially contained components in this query.

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

2 2
4 2
4 1
11 0
1 3