Se te proporciona una cuadrícula de ~n \times n~ que representa el mapa de un bosque. Cada casilla está vacía o contiene un árbol. Tu tarea consiste en procesar ~q~ consultas de los siguientes tipos:

1. Cambiar el estado (vacío/árbol) de una casilla.
2. ¿Cuántos árboles hay dentro de un rectángulo en el bosque?

Entrada

• La primera línea de entrada contiene dos números enteros, ~n~ y ~q~: el tamaño del bosque y el número de consultas.
• A continuación, hay ~n~ líneas que describen el bosque. Cada línea tiene ~n~ caracteres: un ~.~ representa una casilla vacía y un ~*~ representa un árbol.
• Finalmente, hay ~q~ líneas que describen las consultas. El formato de cada línea es "~1~ ~y~ ~x~" ó "~2~ ~y_1~ ~x_1~ ~y_2~ ~x_2~".

Salida

Imprime la respuesta a cada consulta del segundo tipo.

Restricciones

• ~1 \leq n \leq 1000~
• ~1 \leq q \leq 2 \cdot 10^5~
• ~1 \leq y,x \leq n~
• ~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 2 3 4
1 3 3
2 2 2 3 4

Ejemplo de Salida

3
4