CF1920F1.Smooth Sailing (Easy Version)

The only difference between the two versions of this problem is the constraint on $q$. You can make hacks only if both versions of the problem are solved.

Thomas is sailing around an island surrounded by the ocean. The ocean and island can be represented by a grid with $n$ rows and $m$ columns. The rows are numbered from $1$ to $n$ from top to bottom, and the columns are numbered from $1$ to $m$ from left to right. The position of a cell at row $r$ and column $c$ can be represented as $(r, c)$. Below is an example of a valid grid.

Example of a valid grid

There are three types of cells: island, ocean and underwater volcano. Cells representing the island are marked with a '#', cells representing the ocean are marked with a '.', and cells representing an underwater volcano are marked with a 'v'. It is guaranteed that there is at least one island cell and at least one underwater volcano cell. It is also guaranteed that the set of all island cells forms a single connected component$^{\dagger}$ and the set of all ocean cells and underwater volcano cells forms a single connected component. Additionally, it is guaranteed that there are no island cells at the edge of the grid (that is, at row $1$, at row $n$, at column $1$, and at column $m$).

Define a round trip starting from cell $(x, y)$ as a path Thomas takes which satisfies the following conditions:

• The path starts and ends at $(x, y)$.
• If Thomas is at cell $(i, j)$, he can go to cells $(i+1, j)$, $(i-1, j)$, $(i, j-1)$, and $(i, j+1)$ as long as the destination cell is an ocean cell or an underwater volcano cell and is still inside the grid. Note that it is allowed for Thomas to visit the same cell multiple times in the same round trip.
• The path must go around the island and fully encircle it. Some path $p$ fully encircles the island if it is impossible to go from an island cell to a cell on the grid border by only traveling to adjacent on a side or diagonal cells without visiting a cell on path $p$. In the image below, the path starting from $(2, 2)$, going to $(1, 3)$, and going back to $(2, 2)$ the other way does not fully encircle the island and is not considered a round trip.

Example of a path that does not fully encircle the island

The safety of a round trip is the minimum Manhattan distance$^{\ddagger}$ from a cell on the round trip to an underwater volcano (note that the presence of island cells does not impact this distance).

You have $q$ queries. A query can be represented as $(x, y)$ and for every query, you want to find the maximum safety of a round trip starting from $(x, y)$. It is guaranteed that $(x, y)$ is an ocean cell or an underwater volcano cell.

$^{\dagger}$A set of cells forms a single connected component if from any cell of this set it is possible to reach any other cell of this set by moving only through the cells of this set, each time going to a cell with a common side.

$^{\ddagger}$Manhattan distance between cells $(r_1, c_1)$ and $(r_2, c_2)$ is equal to $|r_1 - r_2| + |c_1 - c_2|$.

该题两个版本的唯一区别在于对 $q$ 的约束条件。只有当两个版本的题目均被解决时，才允许进行 hack。

托马斯正在围绕一座被海洋包围的岛屿航行。海洋与岛屿可用一个 $n$ 行 $m$ 列的网格表示。行号从上到下依次为 $1$ 至 $n$，列号从左到右依次为 $1$ 至 $m$。位于第 $r$ 行、第 $c$ 列的格子可表示为 $(r, c)$。下图是一个合法网格的示例：

合法网格示例

格子共分三种类型：岛屿、海洋和水下火山。代表岛屿的格子用字符 # 标记，代表海洋的格子用字符 . 标记，代表水下火山的格子用字符 v 标记。保证至少存在一个岛屿格子和至少一个水下火山格子。还保证所有岛屿格子构成一个单连通块$^{\dagger}$，且所有海洋格子与水下火山格子共同构成一个单连通块。此外，保证网格边界（即第 $1$ 行、第 $n$ 行、第 $1$ 列、第 $m$ 列）上不存在岛屿格子。

定义从格子 $(x, y)$ 出发的一次环形航行为托马斯所走的一条路径，满足以下条件：

• 路径起点与终点均为 $(x, y)$；
• 若托马斯当前位于格子 $(i, j)$，则他可移动至 $(i+1, j)$、$(i-1, j)$、$(i, j-1)$ 或 $(i, j+1)$，前提是目标格子在网格范围内，且为海洋格子或水下火山格子。注意：在同一次环形航行中，允许重复访问同一格子；
• 该路径必须环绕岛屿一周，并完全包围该岛屿。路径 $p$ 被称为完全包围岛屿，当且仅当：不存在一条从任意岛屿格子出发、仅经由与之上下左右或对角线相邻的格子（即八邻域）到达网格边界的路径，且该路径不经过 $p$ 上的任何格子。下图中，从 $(2, 2)$ 出发、前往 $(1, 3)$、再沿另一路径返回 $(2, 2)$ 的路径未完全包围岛屿，因此不被视为一次环形航行。

未完全包围岛屿的路径示例

一次环形航行的安全性定义为：该路径上所有格子到任意一个水下火山格子的最小曼哈顿距离$^{\ddagger}$（注意：岛屿格子的存在不影响该距离计算）。

你将收到 $q$ 个查询。每个查询形如 $(x, y)$；对每个查询，你需要求出从 $(x, y)$ 出发的所有环形航行中，所能达到的最大安全性。保证 $(x, y)$ 是海洋格子或水下火山格子。

$^{\dagger}$ 若一个格子集合中，任意两个格子均可通过仅经过该集合内格子（每次移动至有公共边的相邻格子）相互到达，则称该集合构成一个单连通块。

$^{\ddagger}$ 格子 $(r_1, c_1)$ 与 $(r_2, c_2)$ 之间的曼哈顿距离定义为 $|r_1 - r_2| + |c_1 - c_2|$。

The first line contains three integers $n$, $m$, and $q$ ($3 \leq n, m \leq 10^5$, $9 \leq n \cdot m \leq 3 \cdot 10^5$, $1 \leq q \leq 5$) — the number of rows and columns of the grid and the number of queries.

Each of the following $n$ lines contains $m$ characters describing the cells of the grid. The character '#' denotes an island cell, '.' denotes an ocean cell, and 'v' denotes an underwater volcano cell.

It is guaranteed that there is at least one island cell and at least one underwater volcano cell. It is guaranteed that the set of all island cells forms a single connected component and the set of all ocean cells and underwater volcano cells forms a single connected component. Also, it is guaranteed that there are no island cells at the edge of the grid (that is, at the row $1$, at the row $n$, at the column $1$, and at the column $m$).

The following $q$ lines describe the queries. Each of these lines contains two integers $x$ and $y$ ($1 \leq x \leq n$, $1 \leq y \leq m$) denoting a round trip starting from $(x, y)$.

It is guaranteed that $(x, y)$ is an ocean cell or an underwater volcano cell.

第一行包含三个整数 $n$、$m$ 和 $q$（$3 \leq n, m \leq 10^5$，$9 \leq n \cdot m \leq 3 \cdot 10^5$，$1 \leq q \leq 5$），分别表示网格的行数、列数以及查询次数。

接下来的 $n$ 行，每行包含 $m$ 个字符，用于描述网格的各个单元格。字符 # 表示陆地单元格，. 表示海洋单元格，v 表示水下火山单元格。

保证至少存在一个陆地单元格和至少一个水下火山单元格；保证所有陆地单元格构成一个连通块，且所有海洋单元格与水下火山单元格共同构成一个连通块。此外，保证网格边缘（即第 $1$ 行、第 $n$ 行、第 $1$ 列、第 $m$ 列）上不存在陆地单元格。

接下来的 $q$ 行描述各次查询。每行包含两个整数 $x$ 和 $y$（$1 \leq x \leq n$，$1 \leq y \leq m$），表示一次从坐标 $(x, y)$ 出发的往返行程。

保证 $(x, y)$ 是一个海洋单元格或水下火山单元格。

For each query, output a single integer — the maximum safety of a round trip starting from the specified position.

对于每个查询，输出一个整数——从指定位置出发的往返行程的最大安全性。

For the first example, the image below shows an optimal round trip starting from $(1, 1)$. The round trip has a safety of $3$ as the minimum Manhattan distance from a cell on the round trip to an underwater volcano is $3$.

Example of an optimal round trip

For the fourth example, remember that it is allowed for Thomas to visit the same cell multiple times in the same round trip. For example, doing so is necessary for the round trip starting from $(7, 6)$.

对于第一个样例，下方图片展示了一条从 $(1, 1)$ 出发的最优环形路径。该环形路径的安全性为 $3$，因为路径上任意一个格子到最近的水下火山的曼哈顿距离的最小值为 $3$。

最优环形路径示例

对于第四个样例，请注意：托马斯在同一次环形路径中可以多次访问同一个格子。例如，从 $(7, 6)$ 出发的环形路径就必须如此操作。