병렬 실행의 기댓값

하나의 프로세서가 두 프로그램을 병렬로 실행할 때, 공유 변수들이 최종적으로 어떤 값을 가지게 되는지 예측하려고 한다. 프로그램은 다음 문법을 따르는 명령들의 나열이다.

<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 명령은 Add 대신 Sub를 사용한다는 점만 다르고 위와 동일하게 번역된다.

프로세서는 두 기계어 프로그램을 각각 첫 명령부터 실행한다. 매 단계마다 두 프로그램 중 하나를 균등한 확률로 무작위로 선택하여 그 프로그램의 다음 명령 하나를 실행한다. 한 프로그램이 끝에 도달하면 다른 프로그램의 남은 명령들을 순서대로 끝까지 실행한 뒤 멈춘다.

모든 변수는 두 프로그램이 공유하지만, 레지스터 집합(R1, R2)은 프로그램마다 따로 가진다. 모든 변수의 초기값은 $0$이다. 각 변수에 대해, 가능한 모든 무작위 실행에 걸친 최종 값의 기댓값을 구하여라.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10$)가 주어진다. 각 테스트 케이스는 두 프로그램의 쌍으로 이루어진다. 각 프로그램은 한 줄에 명령 하나씩 적힌 여러 줄로 구성되며, END라는 단어만 있는 줄로 끝난다. END라는 이름의 변수는 없다. 한 테스트 케이스의 두 프로그램 사이에 빈 줄은 없다. 각 프로그램의 줄 수는 $1$ 이상 $25$ 이하이며, 두 프로그램에 등장하는 서로 다른 변수는 모두 합쳐 $10$개 이하이다.

각 테스트 케이스마다 모든 변수의 최종 값의 기댓값을, 변수 이름의 알파벳 순서(숫자가 문자보다 앞선다)로 한 줄에 하나씩 출력한다. 서로 다른 테스트 케이스의 출력은 정확히 한 개의 빈 줄로 구분한다. 각 값은 소수점 아래 넷째 자리까지 반올림하여 출력하고, 소수점 뒤의 0도 생략하지 않는다(예: 1.2가 아니라 1.2000).