Description

At the beginning, he will tell you the current state of this land, but Xiao D has some pretend operations and wants you to perform them for him:

1. Xiao D specifies $w$ positions and wants to know which of these positions has the largest soaking range if he goes down to soak at that position. The soaking range is defined as the number of positions reachable from the specified position by moving in the four directions up, down, left, and right. If the queried position is soil, then the range is $0$. If multiple positions tie for the maximum, output the one that appears earlier in the given order. The positions are indexed as $1, 2, \ldots, w$.

2. Xiao D specifies $w$ positions. He will use magic to toggle the terrain of these $w$ places in order. That is, if the original position is soil, it becomes a hot spring; if the original position is a hot spring, it becomes soil. Because Xiao D does not want the activity range to shrink too quickly, when turning a hot spring into soil he will not split a connected region.

Input Format

The first line contains two integers, $N, M$, representing the size of the land.

The next $N$ lines each contain $M$ characters, either . (representing a hot spring) or * (representing soil).

The $(N+2)$-th line contains an integer $Q$, the number of operations.

In each of the next $Q$ lines, first read two integers $opt$ and $w$, representing the operation type and the number of specified points. On the same line, there are also $2w$ numbers $x_{1}, y_{1}, x_{2}, y_{2}, \ldots, x_{w}, y_{w}$, which represent the $w$ operation positions $(x_{1}, y_{1}), (x_{2}, y_{2}), \ldots, (x_{w}, y_{w})$.

Output Format

For each operation of type $1$, output the answer to the query on a new line.

5 5
.*...
.****
*....
*****
.....
3
1 2 1 1 1 3
2 1 3 1
1 2 1 1 1 3

2
1

Hint

• For $30\%$ of the testdata, $N, M \le 100, \sum w \le 100$.
• For $70\%$ of the testdata, $N, M \le 1000$.
• Constraints: for $100\%$ of the testdata, $1 \le NM, Q \le 10^{6}, \sum w \le 10^{6}, w \ge 1$.
• The testdata is generated on Windows.

Translated by ChatGPT 5