Se le proporciona una cuadrícula de ~n x n~ que representa el mapa de un bosque. Cada casilla está vacía o contiene un árbol. La casilla superior izquierda tiene coordenadas ~(1,1)~ y la casilla inferior derecha tiene coordenadas ~(n,n)~. Su tarea es procesar ~q~ consultas de la forma: ¿cuántos árboles hay dentro de un rectángulo dado en el bosque?

Entrada

• La primera línea de entrada tiene dos enteros ~n~ y ~q~: el tamaño del bosque y el número de consultas.
• Luego, hay ~n~ líneas que describen el bosque. Cada línea tiene ~n~ caracteres: un punto es una casilla vacía y ~*~ es un árbol.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea tiene cuatro enteros ~y_1, x_1, y_2, x_2~, correspondientes a las esquinas de un rectángulo.

Salida

Imprima el número de árboles dentro de cada rectángulo.

Restricciones

• ~1 \leq n \leq 1000~
• ~1 \leq q \leq 2 \cdot 10^5~
• ~1 \leq y_1 \leq y_2 \leq n~
• ~1 \leq x_1 \leq x_2 \leq n~

Ejemplo de Entrada

4 3
.*..
*.**
**..
****
2 2 3 4
3 1 3 1
1 1 2 2

Ejemplo de Salida

3
1
2