题目描述

这是一个带有修改查询的 H 问题的困难版本。

Lester 和 Delbert 在一家电子公司工作，他们正在开发一个用于连接大型超级计算机两个独立部分的微芯片组件。

该组件基于一个面包板——一种用于微芯片的网格状基板。面包板有 $n$ 行 $m$ 列，每个行-列交叉点是一个节点。此外，面包板的每条边上都有与相邻节点相连的端口：左右两侧各有 $n$ 个端口，上下两侧各有 $m$ 个端口。每个端口在外部连接到面包板所桥接的其中一个部分，并被染成红色或蓝色。

端口之间可以通过在面包板内部布线连接。但必须遵循以下规则：

• 每根导线必须连接一个红色端口和一个蓝色端口，且每个端口最多只能连接一根导线。
• 导线的每一段必须是水平或垂直的，拐弯只能发生在节点处。
• 为避免干扰，导线不能有长度非零的公共部分（但可以共享节点）。此外，一根导线不能重复覆盖同一段长度非零的路径。

面包板的容量是指在满足上述规则的前提下，最多能建立的红-蓝端口连接数。例如，上图所示的面包板容量为 $7$，一种实现七条连接的方式如下图所示。

至此，本题与前一版本的描述完全相同。以下为差异部分。

由于项目开发过程中需求频繁变更，端口的颜色尚未固定。需要处理 $q$ 次修改，每次修改的形式为：“将某一边上一个连续区间内的所有端口颜色翻转（红色变蓝色，蓝色变红色）”。所有修改是持久的，即每次修改都基于前一次修改后的状态。

为了评估这些变更的影响，Lester 和 Delbert 需要在每次修改后计算面包板的容量。请帮助他们高效地完成这一任务。

输入格式

第一行包含三个整数 $n, m, q$（$1 \leq n, m \leq 10^5$，$0 \leq q \leq 10^5$）—— 分别表示面包板的行数、列数和修改次数。

接下来四行描述端口的初始颜色。每行字符为 R 或 B，表示对应端口的颜色。前两行各包含 $n$ 个字符，分别表示左侧和右侧端口从上到下的颜色；后两行各包含 $m$ 个字符，分别表示上方和下方端口从左到右的颜色。

接下来 $q$ 行描述修改操作。每行包含一个字符 $s$ 和两个整数 $l, r$。若 $s$ 为 L 或 R，表示修改左侧或右侧端口，$l$ 和 $r$ 满足 $1 \leq l \leq r \leq n$，表示将第 $l$ 到第 $r$ 行（含）的对应侧端口颜色翻转；若 $s$ 为 U 或 D，表示修改上方或下方端口，$l$ 和 $r$ 满足 $1 \leq l \leq r \leq m$，表示将第 $l$ 到第 $r$ 列（含）的对应侧端口颜色翻转。

输出格式

输出 $q + 1$ 个整数，每行一个，表示经过 $0, \ldots, q$ 次修改后面包板的容量。

数据范围

• $1 \leq n, m \leq 10^5$
• $0 \leq q \leq 10^5$
• $1 \leq l \leq r \leq n$（当 $s$ 为 L 或 R 时）
• $1 \leq l \leq r \leq m$（当 $s$ 为 U 或 D 时）

样例

4 5 4
BBRR
RBBR
BBBBB
RRRRR
L 2 3
R 3 4
U 1 5
D 1 5

7
7
9
4
9

样例说明

初始状态：左侧端口为 BBRR，右侧为 RBBR，上方为 BBBBB，下方为 RRRRR，容量为 7。

第一次修改 L 2 3：左侧第 2 至第 3 行端口颜色翻转，左侧变为 BRBR，容量仍为 7。

第二次修改 R 3 4：右侧第 3 至第 4 行端口颜色翻转，右侧变为 RRBB，容量变为 9。

第三次修改 U 1 5：上方所有端口颜色翻转，上方变为 RRRRR，容量变为 4。

第四次修改 D 1 5：下方所有端口颜色翻转，下方变为 BBBBB，容量变为 9。