题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIX Olimpiada Informatyczna – III etap Rzeki

等到最后一条河被污染，等到最后一棵树被砍掉，等到最后一条鱼被捕捉，然后我们才明白，原来钞票是不能吃的。——印第安谚语

在字节王国，有 $n$ 条河流从南向北沿着直线 $x=i$ $(i=1,2,\ldots,n)$ 流动，还有 $m$ 条河流从西向东沿着直线 $y=j$ $(j=1,2,\ldots,m)$ 流动。每两条河流的交点处都有一座城市。每座城市中，一条河流通过隧道流过，不与另一条混合。过去，每座城市都从其所在的河流取水。然而如今，一些河流污染严重，已无法净化水质，城市不得不从其他河流运水。运水成本等于城市到河流直线的距离。运水使用的是沿河流分布的双向公路，重卡可以通行（河流流向不影响运水）。

遗憾的是，字节王国的预算有限，可能无法为所有城市供水。更复杂的是，有些河流会被净化，有些又会重新污染。

请你编写一个程序，读取河流的当前状态，并支持两种操作：更改河流状态，以及回答在给定预算下最多能为多少城市供水。

输入格式

输入的第一行包含三个整数 $n, m, z$ $(1 \leq n, m, z \leq 100000)$，分别表示南北向河流数、东西向河流数和操作次数。

第二行是一个长度为 $n$ 的字符串，由 + 和 - 组成；第 $i$ 个字符表示第 $i$ 条南北向河流的状态：+ 表示干净，- 表示污染。第三行是一个长度为 $m$ 的字符串，以相同格式描述东西向河流的初始状态。

接下来的 $z$ 行描述操作，每行格式为以下之一：

• $\texttt{Z}\ c$：询问在预算 $c$ $(0 \leq c \leq 10^{18})$ 下，最多能为多少城市供水；
• $\texttt{N}\ i$：第 $i$ $(1 \leq i \leq n)$ 条南北向河流状态改变（干净变为污染，或污染变为干净）；
• $\texttt{M}\ i$：第 $i$ $(1 \leq i \leq m)$ 条东西向河流状态改变。

输出格式

对于每个 $\texttt{Z}$ 类型的询问，输出一行一个整数，表示在给定预算下最多能供水的城市数量。

3 4 11
--+
+++-
Z 1
M 1
M 2
M 3
Z 7
N 3
Z 1000000000000000000
M 2
N 2
Z 4
Z 1000000000000000000

11
9
0
10
12

提示

样例 1 解释

初始状态下，实线表示干净河流，虚线表示污染河流，共有 $12$ 座城市位于交点处。

第一个询问 $\texttt{Z}\ 1$：城市 $(1,4)$ 和 $(2,4)$ 的运水成本为 $1$，因此只能放弃一座，其余 $10$ 座成本为 $0$，故答案为 $11$。

操作 $\texttt{M}\ 1$、$\texttt{M}\ 2$、$\texttt{M}\ 3$ 后，仅 $4$ 座城市有直接干净河流。询问 $\texttt{Z}\ 7$：预算 $7$ 可额外为 $x=2$ 上的 $4$ 座和 $x=1$ 上的 $1$ 座供水，总计 $9$ 座。

附加样例

1. 该样例满足 $n=m=11$，仅第 $6$ 条南北向和东西向河流干净，询问预算 $0, 1, \ldots, 220$；
2. 该样例满足 $n=100000, m=1$，每次询问时恰有一条干净河流（对 $1 \leq i \leq 33333$，先净化第 $3i$ 条河流，询问成本 $2500000000$，再污染第 $3i$ 条河流）。

详细子任务附加限制及分值如下表所示。