Description

侦探事务所的网络正在扩展。新的事务所通过计算机电缆与已有事务所连接。电缆有两种类型——光缆和量子缆——它们传递信号的速度不同。信号通过光缆和量子缆在两个事务所之间传递所需的时间分别为 $T_1$ 和 $T_2$。任意两个事务所之间最多只能有一根电缆，并且只能是其中一种类型。

侦探分为两种级别：技术级和社交级。每位侦探只属于其中一个级别。

新事务所的建设和安装流程如下：当有新事务所的请求被提出且符合规则时，新事务所会被建立，并逐步由两种级别的侦探入驻。

新事务所的请求由两位侦探提出，设为 A 和 B，他们属于不同的级别，并且分别位于不同的事务所。假设第一位侦探在事务所 OA，第二位侦探在事务所 OB。出于安全考虑，OA 和 OB 之间不能有直接连接。管理部门保证不会有来自直接相连事务所的请求，因为每位侦探都明白这样做的危险。

假设新建的事务所为 ON。ON 只能与那些已存在的事务所（记为 OE）连接，且 OE 必须与 OA 或 OB 至少有一个已经连接。ON 会与所有满足以下条件和规范的事务所建立连接。

两种级别的侦探对电缆的可靠性有不同看法。技术级侦探认为 ON 与 OE 之间的连接类型应与其当前事务所与 OE 之间的连接类型相同。社交级侦探则认为 ON 与 OE 之间的连接类型应与其当前事务所与 OE 之间的连接类型不同。因此，总部制定了以下新电缆的规则：

• 当 OE 只与 OA 和 OB 中的一个事务所连接时，ON 与 OE 之间的连接类型由与 OE 相连事务所中的侦探决定。
• 当 OE 同时与 OA 和 OB 相连，且侦探 A 和 B 对 ON 与 OE 之间的连接类型意见不一致时，则不建立连接。
• 当 OE 同时与 OA 和 OB 相连，且侦探 A 和 B 对 ON 与 OE 之间的连接类型意见一致时，则建立连接，但连接类型应与他们一致意见的类型相反。

现在，需要一个应用程序来跟踪所有事务所及其之间的电缆连接情况。

总部位于编号为 0 的事务所。每当新事务所建成后，总部需要获知从总部出发，通过一系列连接能够到达的所有其他事务所与总部之间距离的总和。两个事务所之间的距离是信号通过电缆从一个事务所传递到另一个事务所所需的最短时间，假设信号在路径上的任何事务所内部都不消耗额外时间。

Input Format

输入的第一行包含五个整数 $N, M, R, T_1, T_2$（$1 < N \leq 5; 0 \leq M \leq \binom{N}{2}; 0 \leq R \leq 10^5; 0 \leq T_1, T_2 \leq 100$），$N$ 表示已有事务所的数量，$M$ 表示已有事务所之间的电缆总数，$R$ 表示新事务所的请求数，$T_1$ 和 $T_2$ 分别表示信号通过光缆和量子缆所需的时间。

事务所编号为 $0, 1, \cdots, N-1$。接下来的 $M$ 行，每行包含两个整数 $a$ 和 $b$（$0 \leq a \neq b < N$）以及一个字符“O”或“Q”。整数表示连接的事务所编号，字符表示连接它们的电缆类型（光缆或量子缆）。

接下来有 $R$ 行，每行表示一个新事务所的请求。第 $i$ 个请求（请求编号从 0 开始）包含两个整数 $a$ 和 $b$（$0 \leq a \neq b < N+i$），表示提出请求的两位侦探所在的事务所编号。假设技术级侦探总是排在前面。此外，保证不会有来自直接相连事务所的请求。

Output Format

对于输入中的每个请求，输出一行，从总部出发，通过一系列连接能够到达的所有其他事务所与总部之间距离的总和。

4 3 1 1 100
0 1 Q
1 2 Q
2 3 Q
3 1

601

5 3 2 1 100
0 1 Q
1 2 O
3 4 O
0 2
5 4

302
806

Hint

由 ChatGPT 4.1 翻译