Чтобы выразить праздничный дух, коровы хотят нарисовать картину! Она — сетка $R$ $\times$ $C$ $(1 \le R \le 50,000; 1 \le C \le 15)$ единичных квадратов, каждый0 или1. Строки нумеруются $1,\ldots,R$, столбцы $1,\ldots,C$.
Времени мало, и коровы обратились к соседям севернее границы. Под заботливым руководством лося Canmuu они построили машину, бросающую краску целыми вёдрами! Изначально вся сетка0, машина красит прямоугольник цветом0 или1. Canmuu предлагает $Q$ операций $(1 \le Q \le 10,000)$; операция $i$ задаётся пятью целыми $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)$ и красит цветом $X_{i}$ все клетки в строках от $R1_{i}$ до $R2_{i}$ и столбцах от $C1_{i}$ до $C2_{i}$ включительно.
Так легко ошибиться, поэтому Canmuu просит определить после каждой операции число клеток правильного цвета.
Ограничение памяти:64 MB
Ограничение времени:1.5 секунды
Входные данные
- Строка1: три целых через пробел $R$, $C$, $Q$.
- Строки $2,\ldots,R+1$: строка $i+1$ содержит $C$ символов '0' или '1', представляющих строку $i$ сетки.
- Строки $R+2,\ldots,R+Q+1$: строка $R+i+1$ содержит пять целых через пробел, задающих покраску: $R1_{i}$, $R2_{i}$, $C1_{i}$, $C2_{i}$, $X_{i}$.
Выходные данные
- Строки $1,\ldots,Q$: в строке $i+1$ выведите одно целое — число совпадающих клеток после операции $i$.
Примеры
Входные данные 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
Выходные данные 1
113 94 95 91 87 93 91 87 93 93
Примечание
Коровы хотят нарисовать праздничное дерево.
После первой операции сетка такова:
000000000000000 000000000000000 000000000000000 000000000000000 011111111111110 011111111111110 011111111111110 011111111111110 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000 000000000000000
113 клеток совпадают с соответствующими клетками изображения дерева; ниже отмечены 'x' (остальные биты показаны после первого броска краски):
0000000x0000000 000000xxx000000 00000xxxxx00000 0000xxxxxxx0000 0xx111111111xx0 0xxx1111111xxx0 0xx111111111xx0 0x11111111111x0 000xxxxxxxxx000 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 00xxxxxxxxxxx00 0xxxxxxxxxxxxx0 xxxxxxxxxxxxxxx 000000xxx000000 000000xxx000000 000000xxx000000
Авторы задачи: Brian Hamrick и Neal Wu, 2008