CF1920F2.Smooth Sailing (Hard 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 3 \cdot 10^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 3 \cdot 10^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$。

最优环形路径示例

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