这是问题 H 的更简单版本,无需修改查询。
莱斯特和德尔伯特在一家电子公司工作。他们目前正在开发一种微芯片组件,用于连接大型超级计算机的两个独立部分。
该组件构建在面包板的顶部 - 微芯片的网格状底座。面包板有 $$$n$$$ 行和 $$$m$$$ 列,每个行列交集包含一个节点。此外,面包板的每一侧都有可以连接到相邻节点的端口。左侧和右侧各有 $$$n$$$ 端口,顶部和底部各有 $$$m$$$ 端口。每个端口在外部连接到由面包板桥接的部件之一,并且分别为红色或蓝色。
端口可以通过面包板内部的电线进行连接。但是,有一些规则需要遵循:
- 每根电线应连接一个红色端口和一个蓝色端口,并且每个端口最多应连接到一根电线。
- 电线的每一部分都应水平或垂直,并且只能在其中一个节点处转弯。
- 为了避免干扰,电线不能有非零长度的公共部分(但可以有公共节点)。此外,一根电线不能两次覆盖同一个非零长度的线段。
面包板的容量是根据上述规则可以进行的最大红蓝线连接数。例如,上面的面包板的容量为 $$$7$$$,建立七个连接的一种方法如下图所示。
到目前为止,两个版本的声明是相同的。差异如下。
鉴于当前的面包板配置,帮助 Lester 和 Delbert 有效地找到其容量。
输入
第一行包含三个整数 $$$n, m, q$$$ ($$$1 \leq n, m \leq 10^5$$$, $$$\pmb{q = 0}$$$)。 $$$n$$$ 和 $$$m$$$ 分别是面包板的行数和列数。在此版本中,$$$q$$$ 始终为零,并且仅用于与较难版本保持一致。
接下来的四行描述端口的初始颜色。这些行中的每个字符都是 R 或 B,具体取决于相应端口的颜色。前两行各包含$$$n$$$字符,从上到下分别描述左右两侧的端口。最后两行各包含$$$m$$$字符,从左到右分别描述上下两侧的端口。
输出
打印一个整数——给定的面包板容量。
示例
输入 #1
4 5 0 BBRR RBBR BBBBB RRRRR
输出 #1
7