CF1368H2 Breadboard Capacity (hard version)

实验板有 $n$ 行 $m$ 列，每个行列交叉处有一个节点。试验板每侧都有端口。左、右侧各 $n$ 个端口，上、下侧各 $m$ 个端口。每个端口是红色或蓝色。 端口可通过导线连接。 - 每根导线连接一红色端口和一蓝色端口，每个端口最多连一条导线。 - 导线的每个部分水平或垂直，只能在节点处拐弯。 - 导线不能在节点之外的地方和其他导线相交（也不可以和自己相交）。 试验板的容量是根据上述规则导线数量的最大值。 端口颜色未固定，有 $q$ 次修改。每次修改，在一条边上的连续区间内，端口颜色反转。 计算每次修改后试验板容量。

The first line contains three integers $ n, m, q $ ( $ 1 \leq n, m \leq 10^5 $ , $ 0 \leq q \leq 10^5 $ ) — the number of rows and columns of the breadboard, and the number of modifications respectively. The next four lines describe initial coloring of the ports. Each character in these lines is either R or B, depending on the coloring of the respective port. The first two of these lines contain $ n $ characters each, and describe ports on the left and right sides respectively from top to bottom. The last two lines contain $ m $ characters each, and describe ports on the top and bottom sides respectively from left to right. The next $ q $ lines describe modifications. Each of these lines contains a character $ s $ , followed by two integers $ l $ and $ r $ . If $ s $ is L or R, the modification is concerned with ports on the left/right side respectively, $ l $ and $ r $ satisfy $ 1 \leq l \leq r \leq n $ , and ports in rows between $ l $ and $ r $ (inclusive) on the side switch colors. Similarly, if $ s $ is U or D, then $ 1 \leq l \leq r \leq m $ , and ports in columns between $ l $ and $ r $ (inclusive) on the top/bottom side respectively switch colors.

Print $ q + 1 $ integers, one per line — the breadboard capacity after $ 0, \ldots, q $ modifications have been made to the initial coloring.