Aby pokazać świąteczny nastrój, krowy chcą namalować obraz! Jest siatką $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ jednostkowych kwadratów, każdy0 lub1. Wiersze numerowane $1,\ldots,R$, kolumny $1,\ldots,C$.
Nie mając czasu, proszą o pomoc sąsiadów na północ od granicy. Pod życzliwym nadzorem łosia Canmuu budują maszynę rzucającą całe wiadra farby! Początkowo cała siatka jest0; maszyna maluje prostokąt kolorem0 lub1. Canmuu proponuje $Q$ operacji $(1 \le Q \le 10,000)$; operacja $i$ to pięć całkowitych $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)$ i maluje kolorem $X_{i}$ wszystkie pola w wierszach od $R1_{i}$ do $R2_{i}$ i kolumnach od $C1_{i}$ do $C2_{i}$, z końcami.
Łatwo tak popełnić błędy, więc Canmuu prosi określić liczbę kwadratów właściwego koloru po każdej operacji.
Limit pamięci:64 MB
Limit czasu:1.5 sekundy
Wejście
- Wiersz1: trzy całkowite oddzielone spacjami $R$, $C$, $Q$.
- Wiersze $2,\ldots,R+1$: wiersz $i+1$ ma $C$ znaków '0' lub '1', opisujących wiersz $i$.
- Wiersze $R+2,\ldots,R+Q+1$: wiersz $R+i+1$ ma pięć całkowitych oddzielonych spacjami dla operacji: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Wyjście
- Wiersze $1,\ldots,Q$: w wierszu $i+1$ wypisz jedną całkowitą, liczbę zgodnych pól po operacji $i$.
Przykład
Wejście 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
Wyjście 1
113 94 95 91 87 93 91 87 93 93
Uwagi
Krowy chcą namalować świąteczne drzewo.
Po pierwszej operacji siatka wygląda tak:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 kwadratów zgadza się z odpowiadającymi polami drzewa; oznaczone poniżej 'x' (pozostałe bity pokazują stan po pierwszym rzucie farby):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Autorzy zadania: Brian Hamrick i Neal Wu, 2008