Julia 拥有一个由 $h \cdot w$ 个比特组成的矩形网格，排列为 $h$ 行 $w$ 列，其中行数较小（$h \le 8$）。行从上到下编号为 $1$ 到 $h$，列从左到右编号为 $1$ 到 $w$。比特的值为 $0$ 或 $1$，对一个比特取反意味着将其值翻转：$0$ 变为 $1$，$1$ 变为 $0$。

该网格允许以下三种操作：

• $P\ i\ j$ —— 对第 $i$ 行第 $j$ 列的比特取反，
• $R\ i$ —— 对第 $i$ 行的所有比特取反，
• $K\ j$ —— 对第 $j$ 列的所有比特取反。

Julia 想要清理网格，即将所有比特变为 $0$。实现这一目标所需的最少操作次数被称为网格的“难度”（difficulty）。

顽皮的 Romek 想要破坏 Julia 的计划，并执行了总共 $q$ 次上述三种类型的操作。然而，Romek 没有意识到 Julia 很享受这样的挑战。她观察网格并计算了在 $q+1$ 个时刻（初始时刻以及 Romek 每次操作后）的难度。你能确定这些值吗？

Romek 会永久性地修改网格。Julia 本身不执行任何操作，也不会改变网格。

输入格式

第一行包含三个整数 $h, w$ 和 $q$ ($1 \le h \le 8; 1 \le w, q \le 10^5$)，表示网格的维度和 Romek 执行的操作次数。

接下来的 $h$ 行描述了初始网格：每行包含一个长度为 $w$ 的二进制字符串（字符 $0$ 和 $1$）。

最后 $q$ 行描述了 Romek 的操作，每行的格式为：“$P\ i\ j$”、“$R\ i$”或“$K\ j$” ($1 \le i \le h; 1 \le j \le w$)。

输出格式

输出 $q+1$ 个整数（每行一个）——初始网格的难度，以及 Romek 每次操作后网格的难度。

样例

输入 1

3 4 6
1010
1101
0010
R 2
P 3 1
K 2
P 2 1
K 4
P 3 4

输出 1

3
2
3
4
3
3
4

说明

该图说明了初始网格和 Romek 的前几次操作。初始网格的难度为 $3$，因为 Julia 可以使用以下操作：$P\ 1\ 1, R\ 2, K\ 3$。

1010    1010    1010    1110    1110
1101 R 2 -> 0010 P 3 1 -> 0010 K 2 -> 0110 P 2 1 -> 1110 K 4 -> ...
0010    0010    1010    1110    1110
难度: 3    2       3       4       3