Para mostrar seu espírito festivo, as vacas querem pintar um quadro! Ele é uma grade $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ de quadrados unitários, cada qual0 ou1. Linhas numeradas $1,\ldots,R$, colunas $1,\ldots,C$.
Com pouco tempo, pedem ajuda aos vizinhos ao norte da fronteira. Sob a gentil supervisão do alce Canmuu, constroem uma máquina que lança baldes inteiros de tinta! A grade começa toda0, e a máquina pinta um retângulo com0 ou1. Canmuu sugere $Q$ operações $(1 \le Q \le 10,000)$; operação $i$ tem cinco inteiros $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)$, pintando de $X_{i}$ cada célula nas linhas de $R1_{i}$ a $R2_{i}$ e colunas de $C1_{i}$ a $C2_{i}$, limites inclusos.
É fácil cometer erros assim; Canmuu pede determinar após cada operação quantos quadrados têm a cor correta.
Limite de memória:64 MB
Limite de tempo:1.5 segundos
Entrada
- Linha1: três inteiros separados por espaços $R$, $C$, $Q$.
- Linhas $2,\ldots,R+1$: linha $i+1$ contém $C$ caracteres '0' ou '1', representando a linha $i$.
- Linhas $R+2,\ldots,R+Q+1$: linha $R+i+1$ contém cinco inteiros separados por espaços de uma operação: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Saída
- Linhas $1,\ldots,Q$: na linha $i+1$ imprima um inteiro, a quantidade de células coincidentes após operação $i$.
Exemplos
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
Saída 1
113 94 95 91 87 93 91 87 93 93
Nota
As vacas querem pintar uma árvore festiva.
Após a primeira operação a grade é:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 quadrados coincidem com os correspondentes da árvore; estão marcados com 'x' abaixo (os demais bits são como ficam após a primeira pintura):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Autores do problema: Brian Hamrick e Neal Wu, 2008