[Usaco2009 Hol]Holiday Painting 节日画画

有一块 $R$ 行 $C$ 列的画布，行从上到下编号为 $1,\ldots,R$ ，列从左到右编号为 $1,\ldots,C$ 。画布上每个方格的颜色为 $0$ 或 $1$ ，初始时所有方格的颜色均为 $0$ 。

给定一幅大小为 $R\times C$ 的目标图，接下来依次进行 $Q$ 次涂色操作。每次操作给出 $r_1,r_2,c_1,c_2,\mathit{color}$ ，将所有满足 $r_1\le r\le r_2$ 且 $c_1\le c\le c_2$ 的方格颜色覆盖为 $\mathit{color}$ 。每次操作都在此前操作完成后的画布上继续进行。

每次操作结束后，求当前画布中颜色与目标图对应位置颜色相同的方格数量。

输入格式

第一行包含三个整数 $R,C,Q$ 。

接下来 $R$ 行，每行包含一个长度为 $C$ 、仅由字符 $0$ 和 $1$ 组成的字符串，表示目标图。

接下来 $Q$ 行，每行包含五个整数 $r_1,r_2,c_1,c_2,\mathit{color}$ ，表示一次涂色操作。

输出格式

对于每次操作，输出一行一个整数，表示操作完成后颜色与目标图对应位置颜色相同的方格数量。

样例输入

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\le R\le 5\times 10^4$ ；
$1\le C\le 15$ ；
$1\le Q\le 10^4$ ；
$1\le r_1\le r_2\le R$ ；
$1\le c_1\le c_2\le C$ ；
$\mathit{color}\in\{0,1\}$ 。

来源与许可

本题为 USACO 2009 Holiday 试题「节日画画」，题面与测试数据整理自 BZOJ。

样例 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

输出