Para mostrar su espíritu festivo, las vacas quieren pintar un cuadro. Es una cuadrícula $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ de cuadrados unitarios, cada uno0 o1. Filas numeradas $1,\ldots,R$ y columnas $1,\ldots,C$.
Con poco tiempo, piden ayuda a sus vecinos al norte de la frontera. Bajo la amable supervisión del alce Canmuu construyen una máquina que lanza pintura por cubos enteros. La cuadrícula empieza toda en0; pinta un rectángulo de color0 o1. Canmuu propone $Q$ operaciones $(1 \le Q \le 10,000)$; operación $i$ consta de cinco enteros $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$ $(1 \le R1_i \le R2_i \le R; 1 \le C1_i \le C2_i \le C; 0 \le X_{i} \le 1)$ y pinta de $X_{i}$ cada celda en filas de $R1_{i}$ a $R2_{i}$ y columnas de $C1_{i}$ a $C2_{i}$, ambos extremos incluidos.
Así es fácil equivocarse, por lo que Canmuu pide determinar tras cada operación cuántos cuadrados tienen el color correcto.
Límite de memoria:64 MB
Límite de tiempo:1.5 segundos
Entrada
- Línea1: tres enteros separados por espacios $R$, $C$, $Q$.
- Líneas $2,\ldots,R+1$: línea $i+1$ contiene $C$ caracteres '0' o '1', que representan la fila $i$.
- Líneas $R+2,\ldots,R+Q+1$: línea $R+i+1$ contiene cinco enteros separados por espacios de una operación: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Salida
- Líneas $1,\ldots,Q$: en línea $i+1$ imprime un entero, el número de celdas coincidentes tras operación $i$.
Ejemplos
Entrada 1
17 15 10 111111101111111 111111000111111 111110000011111 111100000001111 111000000000111 111100000001111 111000000000111 110000000000011 111000000000111 110000000000011 100000000000001 110000000000011 100000000000001 000000000000000 111111000111111 111111000111111 111111000111111 5 8 2 14 1 8 17 3 7 1 4 5 10 15 0 7 16 12 14 1 2 17 13 14 0 2 6 2 3 1 13 14 4 8 1 3 6 6 7 1 1 16 10 11 0 7 16 10 10 0
Salida 1
113 94 95 91 87 93 91 87 93 93
Nota
Las vacas quieren pintar un árbol festivo.
Tras la primera operación, la cuadrícula es:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 cuadrados coinciden con los correspondientes del árbol; se marcan con 'x' abajo (los demás bits muestran el estado tras la primera pintura):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Autores del problema: Brian Hamrick y Neal Wu, 2008