侦探办公室的网络正在不断扩大。新的办公室通过计算机电缆与现有的办公室相连。电缆有两种类型：光缆和量子缆，它们传播信号的速度不同。信号通过光缆和量子缆在两个办公室之间传输所需的时间分别为 $T_1$ 和 $T_2$。任意两个办公室之间最多只能有一条电缆，且必须是这两种类型中的一种。

侦探分为两个职级：技术职级和社交职级。每位侦探恰好属于其中一个职级。

建立和安装新办公室的过程如下：当收到建立新办公室的请求且该请求符合规则时，就会建立一个新的办公室，并逐渐由两个职级的侦探入驻。

新办公室的请求来自两名侦探，设为 A 和 B，他们职级不同且居住在不同的办公室。假设第一名侦探居住在办公室 OA，第二名居住在办公室 OB。出于安全考虑，办公室 OA 和 OB 不能共享连接。管理部门保证，不会出现来自两个已共享连接的办公室的请求，因为每位警官都了解此类请求的危险性。

假设 ON 是即将新建的办公室。办公室 ON 只能连接到那些已经存在的办公室（记为 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 之间的连接类型意见一致时，则建立连接。但需要强调的是，其类型与 A 和 B 一致的类型相反。

现在，需要一个应用程序来跟踪所有办公室及其连接的电缆。

总部位于编号为 0 的办公室。在建立新办公室后，总部必须获知总部与其他所有可以通过连接序列到达的办公室之间的距离总和。两个办公室之间的距离是指信号通过电缆从一个办公室传输到另一个办公室的最短时间，假设信号在其路径上的任何办公室内部停留的时间为零。

输入格式

输入的第一行包含五个整数 $N, M, R, T_1, T_2$ ($1 < N \le 5$; $0 \le M \le \binom{N}{2}$; $0 \le R \le 10^5$; $0 \le T_1, T_2 \le 100$)，$N$ 是现有办公室的数量，$M$ 是现有办公室之间电缆的总数，$R$ 是新建办公室的请求数量，$T_1$ 和 $T_2$ 分别是信号通过光缆和量子缆传输的时间。

办公室编号为 $0, 1, \dots, N-1$。接下来的 $M$ 行，每行包含两个整数 $a$ 和 $b$ ($0 \le a \neq b < N$) 以及一个字符 “O” 或 “Q”。整数确定了连接办公室的编号，字符确定了连接它们的电缆类型（光缆或量子缆）。

接下来有 $R$ 行，每行代表一个建立新办公室的请求。第 $i$ 个请求行（请求计数器 $i$ 从 0 开始）包含两个整数 $a$ 和 $b$ ($0 \le a \neq b < N+i$)，即请求的侦探对所在的办公室编号。假设技术职级的侦探所在的办公室总是列在前面。此外，保证不会有请求发生在两个已经有直接连接的办公室之间。

输出格式

对于输入中的每个请求，在单独的一行上打印从总部到所有其他可以通过连接序列到达的办公室的距离总和。

样例

样例输入 1

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

样例输出 1

601

样例输入 2

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

样例输出 2

302
806