题目描述

我们需要预测一个单处理器在运行两个程序并行时的一些行为特征。程序是由以下语法规则定义的命令序列：

< Program > -> < Command > *

< Command > -> < Variable > := < Operand > < Operator > < Operand >

< Operator > -> + | -

< Operand > -> < Variable > | < Constant >

其中，变量 <Variable> 是一个由字母开头（不区分大小写）的最多 20 个字母数字字符（A...Z, a...z, 和 0...9）组成的序列。常量 <Constant> 是一个小于 100 的无符号整数。命令之间的空白或制表符数量可以任意。

在执行之前，程序会被翻译成机器语言。例如，一个形式为 X := Y + Z 的语句会被翻译成以下机器指令集：

Mov R1, Y
Mov R2, Z
Add R1, R2
Mov X, R1

MOV 指令将第二个操作数的内容复制到第一个操作数中。Add（或 Sub）指令将第二个操作数加（或减）到第一个操作数中，并将结果存储在第一个操作数中。注意，Y 和 Z 表示变量或整数常量。对于命令 X := Y - Z 生成的指令与上述类似，只是用 Sub 替换了 Add。

处理器被给予两个机器语言程序，并从第一条指令开始执行它们。在每一步中，处理器随机选择其中一个程序，并执行所选程序的下一条指令。这一过程持续进行，直到其中一个程序到达其结尾。在这种情况下，另一个程序中剩余的指令将按顺序执行到底，然后处理器停止。假设所有变量在两个程序之间共享，但每个程序都有独立的寄存器组。本程序的目标是计算所有变量在所有可能的程序执行中的预期最终值。更具体地说，我们需要考虑两个程序的所有可能执行情况，并为每个变量计算其在不同执行中的最终值的平均值。假设所有变量的初始值均为零。

输入

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10$），表示测试用例的数量，随后是每个测试用例的输入数据。每个测试用例的数据由一对程序组成。每个程序以一系列连续的行表示，每行包含一个命令。程序以包含单词 END 的行结束。你可以假设没有任何程序中的变量被命名为 END。一个测试用例中的两个程序之间没有空行。每个程序至少有一行，最多有 25 行。两个程序中变量的总数不超过 10。

输出

对于每个测试用例，输出文件应按变量名的字母顺序（数字优先于字母）列出所有变量的预期最终值。不同测试用例的输出之间应恰好用一个空行分隔。将输出中的数字四舍五入到小数点后四位。不要省略小数点后的尾随零（例如，写成 1.2000 而不是 1.2）。

输入数据 1

1
S := 1 + 3
END
S := S + S
END

输出数据 1

3.0000

来源

德黑兰 2001