[D] Igor en el Museo

Enlace a Codeforces

Igor está en el Museo y quiere ver tantos cuadros como sea posible.

El Museo se puede representar como un campo rectangular de $n \times m$ celdas. Cada celda está vacía o es infranqueable (no se puede atravesar). Las celdas vacías se señalan con un punto ('.'), y las infranqueables con un asterisco (*). Entre cada dos celdas distintas adyacentes (una vacía y una infranqueable) hay un muro con un cuadro que las separa.

Al comienzo Igor está en alguna de las celdas vacías. En todo momento, Igor se puede mover a cualquiera de las celdas vacías compartiendo uno de sus lados con la actual.

Para varias posiciones iniciales, debes calcular la máxima cantidad de cuadros que puede ver Igor. Igor es capaz de ver un cuadro sólo si está en la celda adyacente al muro que lo contiene. En adición, Igor tiene un montón de tiempo, así que examinará todos los cuadros que estén a su alcance.

Entrada

La primera línea contiene tres enteros $n$, $m$ y $k$ ($3 \leq n, m \leq 1000$, $1 \leq k \leq min(n\cdot m, 100000$) - las dimensiones del museo y la cantidad de posiciones iniciales a procesar.

Cada una de las siguientes $n$ línea contiene $m$ símbolos '.' o '*' - la descripción del museo. Se garantiza que todos las celdas al borde del musero serán infranqueables, de modo que Igor puede salir del Museo.

Cada una de las últimas $k$ líneas contiene dos enteros $x$ e $y$ ($1 \leq x \leq n$, $1 \leq y \leq m$) - la fila y la columna de la posición inicial de Igor, respectivamente. Las filas se numeras de arriba a abajo, y la columnas de izquierda a derecha. Se garantiza que todas las posiciones iniciales serán celdan vacías.

Salida

Imprime $k$ enteros - la cantidad máxima de cuadros que Igor puede ver si comienza en una posición correspondiente.

Ejemplos

input:
5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

output:
6
4
10

input:
4 4 1
****
*..*
*.**
****
3 2

output:
8