F1. Спокойное плавание (простая версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие двух версий этой задачи состоит в ограничении на $$$q$$$. Вы можете делать взломы, только если обе версии задачи решены.

Томас плавает вокруг острова, окружённого океаном. Океан и остров можно представить в виде таблицы с $$$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|$$$.

Входные данные

Первая строка содержит три целых числа $$$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)$$$ является клеткой океана или подводного вулкана.

Выходные данные

Для каждого запроса выведите одно целое число — максимальную безопасность кругового маршрута, начинающегося в указанной клетке.

Примеры
Входные данные
9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7
Выходные данные
3
0
3
Входные данные
3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2
Выходные данные
0
0
0
0
0
Входные данные
14 13 5
.............
.............
.............
...vvvvvvv...
...v.....v...
...v.###.v...
...v.#.#.v...
...v..v..v...
...v..v..v...
....v...v....
.....vvv.....
.............
.............
.............
1 1
7 7
5 6
4 10
13 6
Выходные данные
3
0
1
0
2
Входные данные
10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1
Выходные данные
1
2
3
4
Примечание

Для первого примера на изображении ниже показан оптимальный круговой маршрут, начинающийся в $$$(1, 1)$$$. Безопасность кругового маршрута равна $$$3$$$, так как минимальное манхэттенское расстояние от клетки на круговом маршруте до подводного вулкана равно $$$3$$$.

Пример оптимального кругового маршрута

В четвёртом примере помните, что Томасу разрешается посещать одну и ту же клетку несколько раз за один круговой маршрут. Например, это необходимо для кругового маршрута, начинающегося в $$$(7, 6)$$$.