덧셈

여섯 해 전, 사악한 과학자 Alice가 유아 수준의 지능을 가진 로봇 Bob을 발명했다.

이제 로봇은 여섯 살이며 초등학교에 다닌다. 덧셈은 Bob이 수학에서 처음 배운 연산이다. 뛰어난 추론 능력 덕분에 이제 Bob은 a=2와 b=10로부터 a+b=12임을 알아낼 수 있다.

Alice는 Bob의 덧셈 실력을 시험하고 싶었다. a=2, b=10, c=4 형식의 방정식 몇 개가 Bob에게 주어졌고, Bob은 a+b, a+c 등과 같은 질문의 답을 알아내야 했다.

Alice는 시험지에서 Bob의 답을 하나씩 확인했으며 지금까지 실수는 발견되지 않았지만, 커피 한 잔을 쏟아 주어진 방정식을 잃어버렸다. 하지만 Alice에게는 a+b=12, a+c=6, c+d=5 등 Bob이 맞힌 답 중 일부가 남아 있다. Alice는 답을 확인할 수 있는 방정식을 계속 검사하고 싶어 한다. 예를 들어 a+b=12, a+c=6, c+d=5로부터 b+d=11를 알아낼 수 있으므로 질문 b+d의 답은 확인할 수 있다.

인공지능 기술이 Alice의 통제하에 들어가는 것을 막기 위해, 당신은 Alice의 조수로 위장했다. 이제 Alice는 남은 질문 중 어떤 것의 답을 확인할 수 있는지와 그 답을 알아내 달라고 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

변수 이름은 영문 소문자로 이루어진 문자열이다. 각 이름은 최대 10개의 문자를 포함한다. -200000 ≤ z ≤ 200000 답이 주어진 질문들 사이에는 모순이 없으며, 답을 확인할 수 있다면 그 결과는 정수이다.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 10 1 ≤ N ≤ 10 1 ≤ Q ≤ 10

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 3 1 ≤ N ≤ 5000 1 ≤ Q ≤ 5000

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 올바르게 답한 질문의 수를 나타내는 하나의 정수 N이 주어진다. 다음 N개의 각 줄에는 올바르게 답한 질문 하나가 "x+y=z" 형식으로 주어진다. 여기서 x와 y는 변수 이름이고 z는 십진 정수이다.

다음 줄에는 남은 질문의 수를 나타내는 하나의 정수 Q가 주어진다. 다음 Q개의 각 줄에는 질문 하나가 "x+y" 형식으로 주어진다. 여기서 x와 y는 변수 이름이다.

각 테스트 케이스에서 출력의 첫 번째 줄에는 "Case #x:"를 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 입력의 각 질문 중 답을 확인할 수 있는 질문마다 "x+y=z" 형식으로 답을 한 줄에 출력한다. 여기서 x와 y는 변수 이름이고 z는 십진 정수이다. 질문은 입력에서 주어진 순서와 같은 순서로 나열해야 한다. Alice의 실수를 지적하면 해고당할 것이므로 중복된 질문을 NOT 무시해 주십시오.