Descripción

Maullín logra salir y contempla que hay demasiado por descubrir; no sabe a dónde ir, pero está emocionado por iniciar una aventura. Ahora necesita tu ayuda, ya que él es un caminante en un mar de nubes.
El gato puede ver a su alrededor, pero solo hasta un cierto límite \(k\) debido a la espesa niebla que obstruye la visión. Él quiere saber cuántos y qué tipos de obstáculos tiene a su alrededor en su rango de visión; puede verlos, pero está muy nervioso y pierde la cuenta de cuántos obstáculos hay.

Su visión cubre un área cuadrada centrada en él, de tamaño \((2 * k + 1) * (2 * k + 1)\).

Los obstáculos se representan de la siguiente forma:

• Árbol: *
• Roca: #
• Tronco: -

Los lugares donde Maullín puede pasar están representados por .

Maullín nos puede preguntar desde muchas posiciones. Para cada consulta, nos dirá una posición (x, y) del mapa (indexado en \(1\)) y el tamaño \(k\) de su visión.

Entrada

La primera línea contiene un entero \(n\), (\(n * n\) es el tamaño del mapa).
Seguidos de \(n\) * \(n\) caracteres que representan el mapa.

A continuación, un entero \(q\), el número de consultas.
Cada una de las siguientes \(q\) líneas contiene tres enteros: \(x\), \(y\) y \(k\).

Se asegura que la posición en la que se encuentra Maullín siempre será un .

Salida

Para cada consulta, imprime tres valores separados por espacios:

• La cantidad de árboles, rocas y troncos que Maullín puede ver dentro de su área de visión.

Ejemplo

Entrada

5 
. . - . .
. . . * .
. # . . -
- . . # .
. . . . *
2
3 3 1
3 3 2

Salida

1 2 0
2 2 3

Explicación

Maullín se encuentra en medio del mapa. Primero, tiene una visión de tamaño 1, por lo que solo puede ver lo que está resaltado gris.

Cuando maullín tiene una visión de tamaño 2, puede ver todo el mapa :0

Límites

• \(1 \leq n \leq 1000\)
• \(1 \leq q \leq 2 * 10^5\)
• \(1 \leq x, y \leq n\)
• \(1 \leq k < n\)