只有当最后一棵树被砍倒， 最后一条河流被污染， 最后一条鱼被捕捞， 人类才会发现自己无法用金钱充饥。 ——印第安谚语

在 Bajtocja 有 $n$ 条从南向北流动的河流，沿直线 $x = i$（$i = 1, 2, \ldots, n$）分布；以及 $m$ 条从西向东流动的河流，沿直线 $y = j$（$j = 1, 2, \ldots, m$）分布。

在每一处两条河流的交点都有一座城市。在每座城市中，其中一条河流通过隧道与另一条河流交叉，因此两条河流的水不会混合。过去，每座城市都从经过它的两条河流中取水。

然而如今，一些河流被污染到无法净化水源的程度，因此城市必须从其他河流运水。将水从某条河流运到某个城市的费用等于该城市到这条河流所在直线的距离。运输用水的卡车沿着位于河流旁的双向道路行驶（河流流动方向不影响运输）。

不幸的是，Bajtocja 的预算有限，可能无法为所有城市供水。情况更加复杂的是，有些河流会被清理干净，而有些则会再次受到污染。

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

输入格式

第一行包含三个整数 $n, m, z$（$1 \le n, m, z \le 100,000$），分别表示从南向北流动的河流数量、从西向东流动的河流数量，以及需要处理的操作次数。

第二行包含一个长度为 $n$ 的字符串，由字符 + 和 - 组成；第 $i$ 个字符表示第 $i$ 条向北流动河流的状态：+ 表示该河流是干净的，- 表示被污染。

第三行包含一个长度为 $m$ 的字符串，表示向东流动河流的初始状态，格式相同。

接下来 $z$ 行，每行描述一个操作，格式如下之一：

• Z c —— 查询在预算为 $c$（$0 \le c \le 10^{18}$）的情况下，最多可以为多少个城市供水；
• N i —— 表示第 $i$ 条向北流动的河流改变状态：如果原本是干净的，则变为污染；如果原本是污染的，则变为干净（$1 \le i \le n$）；
• M i —— 表示第 $i$ 条向东流动的河流改变状态（$1 \le i \le m$）。

输出格式

对于输入中每个类型为 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

样例说明

下图表示在执行任何操作之前的情况。实线表示干净的河流，虚线表示被污染的河流。在这些直线的交点处共有 $12$ 座城市。

1 2 3
1
2
3
4

对于第一个查询（Z 1），答案是 $11$。因为向城市 $(1,4)$ 和 $(2,4)$ 供水的费用均为 $1$（因此其中一个城市必须无法供水），而向其余十个城市供水的费用为 $0$。

执行第二个操作（M 1）后，城市 $(1,1)$ 和 $(2,1)$ 失去了对干净河流的直接访问；类似地，在执行第三和第四个操作后，只有四个城市仍然直接位于干净河流的交点上。

因此，对下一个查询（Z 7）的回答为 $9$，因为在预算 $7$ 内，还可以为位于直线 $x = 2$ 上的四个城市以及位于直线 $x = 1$ 上的一个城市供水。

子任务

测试数据分为以下子任务。每个子任务包含一个或多个测试组。